A Privacy-Friendly Approach to Data Valuation
Authors: Jiachen T. Wang
Yuqing Zhu
Yu-Xiang Wang
Ruoxi Jia
Prateek Mittal
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Data Valuation
Differential Privacy
TL;DR: We develop an alternative of KNN-Shapley with improved efficiency and can be easily extended to incorporate differential privacy.

Abstract: Data valuation, a growing field that aims at quantifying the usefulness of individual data sources for training machine learning (ML) models, faces notable yet often overlooked privacy challenges. This paper studies these challenges with a focus on KNN-Shapley, one of the most practical data valuation methods nowadays. We first emphasize the inherent privacy risks of KNN-Shapley, and demonstrate the significant technical challenges in adapting KNN-Shapley to accommodate differential privacy (DP). To overcome these challenges, we introduce TKNN-Shapley, a refined variant of KNN-Shapley that is privacy-friendly, allowing for straightforward modifications to incorporate DP guarantee (DP-TKNN-Shapley). We show that DP-TKNN-Shapley has several advantages and offers a superior privacy-utility tradeoff compared to naively privatized KNN-Shapley. Moreover, even non-private TKNN-Shapley matches KNN-Shapley's performance in discerning data quality. Overall, our findings suggest that TKNN-Shapley is a promising alternative to KNN-Shapley, particularly for real-world applications involving sensitive data.

Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation
Jiachen T. Wang*
Yuqing Zhu UC Santa Barbara yuqinnzzuuucsb.. edu
Princeton University
ciaahaovvang@priiccttoo.eee
Yu-Xiang Wang
Ruoxi Jia"
Prateek Mittal
UC Santa Barbara
Virginia Tech
Princeton University
yuxiangv&cs.
ruoxijia@vt.cm edu
pmittal@ppincetton edu
Abstract
Data valuation aims to quantify the usefulness of individual data sources in training machine learning (ML) models, and a critical aspect of data-centric MI. research. However, data valuation faces significant yet frequently overlooked privacy chal- lenges despite its importance. This paper studies these challenges with a focus KNN-Shapley, one of the most practical data valuation methods nowadays. We first emphasize the inherent privacy risks of KNN-Shapley, and demonstrate the significant technical difficulties in adapting KNN-Shapley accommodate differential privacy (DP). To overcome these challenges, we introduce TKNN- Shapley, refined variant of KNN- AAN-Shapley that is privacy-friendll, allowing for straightforward modifications to incorporate DP guarantee (DP-TK) -UNNSSal-)aall We show that DP-TKNN-SS -Shhaply has several advantages and offers superior crivacy-tillity tradeoff compared to naively privatized KNN-Shapley discerning data quality. Moreover, even non-private TKNN-Shaples achieves comparable performance as KNN-Shapley. Overall, our findings suggest that TKNN-Shapley is promising alternative to KNN-Shapley, particularly for real-world applications involving sensitive data]]
Introduction
Data valuation is an emerging research area that seeks to measure the contribution of individual data sources to the training of machine learning (ML) models. Data valuation is essential in data market- places for ensuring equitable compensation for data owners, and in explainable ML for identifying influential training data. The importance of data valuation is underscored by the DASHBOARD Act introduced the U.S. Senate in 2019 [66], which mandates companies to provide users with an assessment of their data's is economic value. Moreover, OpenAl's Future Plan explicitly highlights "the fair distribution of Al-generated benefits" " as a key question moving forward [51]
Data Shapley. Inspired by cooperative game theory. (23 30) initiated the study of using the Shapley value as a principled approach for data valuation. The Shapley value (56) is famous solution concept from game theory for fairly assigning the total revenue to each player. In typical scenario of data valuation, training data points are collected from different sources, and the data owner of each training data point can be regarded as "player" in cooperative game. "Data Shapley" refers to the method of using the Shapley value as the contribution measure for each data owner. Since its introduction, many
*Corespoondence to Jiachen T. Wang and Ruoxi Jia.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

different variants of Data Shapley have been proposed 129 22, 63 6 39 its effectiveness in quantifying data point contributions to ML model training.
44
69
33
60
reflecting
KNN-Shapley. While being a principled approach for data valuation, the exact calculation of the Shapley value is computationally prohibitive
30 Various approximation algorithms for Data
Shapley have been proposed (30] 28 50 64
62). but these approaches still require substantial computational resources due to model retraining. Fortunately, a breakthrough by [29] showed that computing the exact Data Shapley for K-Nearest Neighbors (KNN), one of the oldest yet still popular ML algorithms, is surprisingly easy and efficient. KNN-Shapley quantifies data value based on KNN's Data Shapley score; it can be applied to large. high-dimensional CV/NLP datasets by calculating the value scores on the last-layer neural network embeddings. Owing to its superior efficiency and effectiveness in discerning data quality, KNN-Shapley is recognized as one of the most practical data valuation techniques nowadays (52). has been applied to various MI. domains
48
44
including active learning (24], continual learning 57 NLP 42 and semi-supervised learning
Motivation: privacy risks in data valuation. In this work, we study a critical, yet often overlooked concern in the deployment of data valuation: privacy leakage associated with data value scores released to data holders. The value of a single data point is always relative to other data points in the training set. This, however, can potentially reveal sensitive information about the rest of data holders in the dataset. This problem becomes even more complex when considering strong threat model where multiple data holders collude, sharing their received data values to determine the membership of particular individual. As data valuation techniques such as KNN-Shapley become increasingly popular and relevant in various applications, understanding and addressing the privacy challenges of data valuation methods is of utmost importance. In this work, we study this critical issue through the applications.
lens of differential privacy (DP) (15), a de-facto standard for
Our technical contributions are listed as follows.
Privacy Risks & Challenges of Privatization for KNN-Shapley (Section We demonstrate that data value scores (specifically KNN-Shapley) indeed serve as a new channel for private information leakage, potentially exposing sensitive information about individuals in the dataset. In particular, we explicitly design a privacy attack (in Appendix B.2.2) where an adversary could infer the pres- ence/absence of certain data points based on the variations in the KNN-Shapley scores, analogous to the classic membership inference attack on ML model (58). Additionally, we highlight the technical challenges in incorporating the current KNN-Shaple technique with differential privacy, such as its large global sensitivity. All these results emphasize the need for a new, privacy-friendde approach to data valuation.
To address the privacy concerns, we derive novel variant of KNN-Shapley. This new method considers the Data Shapley of an alternative form of KNN classifier called Threshold-KNN (TKNN) [5), which takes into account all neighbors within a pre-speeified threshold of a test example, rather than the exact K nearest neighbors. We derive the closed-form formula of Data Shapley for TKNN (i.c.. TKNN-Shapley) We show that it can be computed exactly with exact linear-time computational efficiency over the original KNN-Shapley. DP-TKNN-Shapley (Section 5). Importantly, we recognize that TKNN- IKNN-Shapley only depends on three simple counting queries. Hence, -hapley can be conveniently transformed into a differentially private version by DP's prst-poocssiing property. Moreover, we prove that such a DP variant satisfies several favorable properties, including (1) the high computational efficiency, (2) the capability to withstand collusion among data holders without compromising the privacy guarantee, and (3) the ease of integrating subsampling for privacy amplification.
TKNN-Shapley: an efficient, privacy-friendl data valuation technique (Section 4.2
Numerical experiments (Section 6). We evaluate the performance of TKNN-Shapley across 11 commonly used benchmark datasets and 2 NLP datasets. Key observations include: (1) TKNN- Shapley surpasses KNN-Shaples in terms of computational efficiency; (2) significantly outperforms the naively privatized KNN-Shapley in terms of privacy-utility tradeoff in discerning data quality; (3) even non-private TKNN-Shapley achieves comparable performance as KNN-Shapley.
Overall, our work suggests that TKNN-Shapleg being a effective alternative to the original KNN- ANN-lhapley, signifies milestone toward practical data valuation.
yet more efficient and
2

---

2 Background of Data Valuation
In this section, we formalize the data valuation problem for ML, and review the method of Data Shapley and KNN-Shapley.
Setup Goal. Consider a dataset D == {=i),=_ consisting of N data points where each data point Fi = ( ys) is collected from data owner i. The objective of data valuation is to attribute a score to each training data point 24, reflecting
importance or quality in MI model training. Formally, we aim to determine score vector (0,, ) wherein 62, represents the value of data point 2;. For any reasonable data valuation method, the value of a data point is always relative to other data points in the dataset. For instance, if data point has many duplicates in the dataset, its value will likely be lower. Hence, Φ2. is a function of the leave-one-our dataset D- == D {2;]. We write ds, (D-,,) when we want to stress the dependency of a data value score with the rest of the data points.
Most of the existing data valuation techniques are centered on the concept of function, which maps an input dataset to a score indicating the usefulness of the training set. common choice for utility function the validation accuracy of model trained on the input training set. Formally, for a training set S, utility function v(S) == acc(A(S)), where AA is learning algorithm that takes a dataset S' as input and returns a model; acc(-) a metric function that evaluates the performance of given model, e.g., the classification accuracy hold-out validation set.
Utility Function.
2.1 The Shapley Value
The Shapley value (SV) (56) is a classic concept from game theory to attribute the total gains generated by the coalition of all players. At high level, it appraises each point based on the (weighted) average utility change caused by adding the point into different subsets of the training set. Formally, given utility function v-) and training set D. the Shapley value of a data point 2 E D is defined as
6. (D=::))
1 N
N
N-1
Σ SCD-
(u(SU es()
For notation simplicity, when the context is clear, we omit the utility function and/or leave-onc-out dataset, and write (D-=). dz (v) or Φ depending the specific dependency want to stress.
The popularity of the Shapley value is attributable to the fact that it the unique data value notion satisfying four axioms: Dummy player, Symmetry, Linearity, and Efficiency. We refer the readers to
[23] 30 and the references therein for a detailed discussion about the interpretation and necessity of the four axioms in the MI. context. Here, we introduce the linearity axiom which will be used later.
Theorem 1 (Linearity of the Shapley value (56)). For any of two utility functions U1, and any Q1. 02 E R, we have oz (a1v1 + a202) 01 (v1) 020; (V2).
2.2 KNN-Shapley
Formula 4T) suggests that the exact Shapley value can be computationally prohibitive in general, as it requires evaluating v(S) for all possible subsets S C D. Surprisingly, [29 [1] showed that for K-Nearest Neighbor (KNN), the computation of the exact Data Shapley score is highly efficient. Following its introduction, KNN-Shapley has rapidly gained attention and follow-up works across
diverse areas of machine learning (2 43 42 [ In particular, has been recognized by recent
studies as "the most practical data valuation technique capable of handling large-scale data effectively"
52 33
Specifically, the performance of an unweighted KNN classifier is typically evaluated by its validation
accuracy. For given validation set (vall) [2 (val), N..i, we can define KNN's utility function KKN
l=1
on a non-empty training set S as v KNx
Divan (S) = E. (vvl) eit (S), where
min(K.Is()
RNN (va))
(S) = min K, SS)
Σ
(aatoon)) = =
is the probability of a (soft-label) KNN classifier in predicting the correct label for validation point 2(val) (val))) ((va)) (vva)) In 2 nt (S) (i;;((v()) (val)) is the index of the ith closest data point in
3

---

(x1.111)
Remark (Criteria of Computational Efficiency). As prior data valuation literature [23], we focus the total runtime required to release all data value scores (d . ..... ) This is because, in a practical data valuation scenario (e.g., profit allocation), we rarely want to compute the data Trusted Central Party
Zz (D-z)
Z1
21
ZZ (D-z7)
(x),)))
Zz
(r,(Onn))
...
Data Valuation Algorithm
Zy (x).yn)
PAN (D=2N)
Zy
ZN
(e.g,, KNN-Shapley)
Collected Dataset
Data Value Scores
Return Value Scores to Data Owners
D
The potential privacy risks in data valuation arise from the dependency of the data value score dz, on the rest of the dataset D-z.- Our goal is to privatize Φz,, (D-..) such that it provides strong differential privacy guarantee for the rest of the dataset D D=
Figure 1:
S to (val), When [S] 0, eio (S) is set to the accuracy by random guessing. The distance is measured through suitable metrics such as Eg distance. Here is the main result in [29] 61]:
Theorem 2 IKNN-Shapley 30 61 (simplified version)). Consider the utility function in [ Given a validation data point (val) (val)), (yvaa) and a distance metric d(.,-), ie sort the training
set D {z (zt.y;) y according to d(z;, x.val)) in ascending order, then the Shapley value of each data point Oz E88 corresponding to utility function e u can be computed recursively as follows:
s = fN(),, and & == o f(() for i = 1...., N
where the exact form of functions f((D) can be found in Appendix B.1
..... ...... runtime in total (dominated by the sorting data points in D).
Runtime: the computation of all Shapley values (0
KHW can be achieved in ONN log N)
The Shapley value corresponding to full validation set: for a validation set D(val), recall that KNN Dival) (S) : Egtoah Dival) ((rnn) (S). One can compute the Shapley value corresponding to u D(ma)
SuN
by summing each d ((((va))) ), ie., de (v Ex(aat
& (N.
Theorem tells that for any validation data point z(val), we can compute the exact Shapley value KKN
(D=zii (2(m))) for all 24 E D by using a recursive formula within total runtime of O (N log N). After computing the Shapley value dznn (v2))))) for each 2 (vaa)) E D(val), one compute the Shapley value corresponding to the full validation set by simply taking the sum of each d230 (uRma))) due to the linearity property (Theorem IT of the Shapley value.
value score for only single data point; instead, typical objective is compute the data value scores for all data points within the training set.
3 Privacy Risks & Challenges of Privatization for KNN-Shapley
Scenario. Figure I illlstrates the data valuation scenario and potential privacy leakages considered in our paper. Specifically, centralized, trusted server collects data point 2; from data owner i for each i E [N]. The central server's role is provide each data owner with an assessment of the value of their data 2,, e.g., the KNN-Shapley value 6 A real life example: Mayo Clinic has created a massive digital health patient data marketplace platform 688, where the patients submit part of their medical records onto the platform, and life science companies/labs pay a certain amount of money to purchase patients' data. The platform's 's responsibility to gauge the worth of the data of each patient (i.c., the data owner) to facilitate fair compensation.

---

The privacy risks associated with KNN- KNN-Shapley (as well as other data valuation techniques) arise from the fact that (D==.) depends on other data owners' data D- Consequently, the data value score ga may inadvertently reveal private information (e.g., membership) about the rest of the dataset. The dependency of a data value score on the rest of the dataset is an unavoidable aspect of data valuation, as the value of a data point is inherently a relative quantity determined by its role within the complete dataset.
Remark (Other privacy risks in data valuation). It is important to note that in this work, we do not consider the privacy risks of revealing individuals' data to the central server. This is different type of privacy risk that needs to be addressed using secure multi-party computation (MPC) technique f70J, and it should be used together with differential privacy in practice. In addition, to use KNN-Shapley or many other data valuation techniques, the central server needs to maintain clean, representative validation set, the privacy of which is not considered by this paper.
A Simple Membership Inference (MI) Attack on KNN-Shapley (detailed in Appendix B.2.2). I
-=1
K=3
K=5
K=7
K
K=
K
16
21PPonees
0.55
01515
0.518
0.52
0.57
0.55
0.515
0.6
Phunuue
0,92
0.54
0.313
0.505
0.365
0.588
0.512
0,502
We further illustrate the privacy risks of reveal- ing data value scores with a concrete example. Analogous to the classic membership inference attack on ML model [58), in Appendix [B.2.2 show an example of privacy attack where adversary could infer the presence/absence of certain data points in the dataset based on the variations in the KNN-Shapley scores. The de- sign is analogous to the membership inference attack against ML models via the likelihood ra- tio test [8] The AUROC score of the attack results is shown in Table I
CPU
0.76
01545
0.53
0.573
0.588
0.512
0.613
0.515
Frand
0.225
0.645
0.6
0.992
0.622
0,532
0.535
0.558
Crdiicaed
0.542
0.688
0.665
0.901
0.65
Apdail
0.61
0.588
0.518
Wind
0,595
0.51
0,518
0.525
0.555
0.562
0,305
0.577
Psl
0.728
01625
0.7
0.62
0.52
0.532
0.535
0,552
Table 1: Results of the AUROC of the MI attack proposed in Ap..ndix(B.2.2.on KNN- Shaplly The higher the AUROC score is, the larger the pri- vacy leakage is. The detailed algorithm description and experiment settings can be found in Appendix B.2.2
As we can see, our MIA attack can achieve a detection performance that is better than the random guess (0.5) for most of the settings. On some datasets, the attack performance can achieve > 0.7 AUROC. This demon- strates that privacy leakage in data value scores can indeed lead to non-trivial privacy attacks, and underscores the need for privacy safeguards in data valuation !
3.1 Privatizing KNN-Shapley is Difficult
The growing popularity of data valuation techniques, particularly KNN- ANN-Shappey, underscores the critical need to mitigate the inherent privacy risks. In the quest for privacy protection, differential privacy (DP) [5] has emerged as the leading framework. DP has gained considerable recognition for providing robust, quantifiable privacy guarantees, thereby becoming the de-facto choice in privacy protection. In this section, we introduce the background of DP and highlight the technical difficulties in constructing a differentially private variant for the current version of KNN-Shapley.
Background of Differential Privacy. We use D' N to denote two datasets with an unspecified size over space X. We call two datasets D and D' adjacent (denoted as D ~ D') if we can construct one by adding/removing one data point from the other, e.g., D= D' {z} for some 2 X.
Definition 3 (Differential Privacy (5)). For E, 8 2 O, a randomized algorithm M : N + y is (c, 8) diiferrentiall private if for every pair of adjacent datasets D) D)' and for every subset of possible outputs E. C Y, we have (D)) E E] S e PrM(M(D')) E F) +
That is, (e, S)DP requires that for all adjacent datasets D, D', the output distribution M(D) and M(D') are close, where the closeness measured by the parameters and 8. In our scenario, we would like to modify data valuation function Φz, (D to satisfy (e. 8)-DP in order to protect the privacy of the rest of the dataset D D_ Gaussian mechanism [14] is a common way for privatizing a function; it introduces Gaussian noise aligned with the function's ' global sensitivity, which is the maximum output change when a single data point added/removed from any given dataset.
Definition 4 (Gaussian Mechanism (14.. Define the global sensitivity of a function f Nx -, Rd
as A2( supD> (D) f(D'))2- The Gaussian mechanism M with noise level a is then
given by M(D) = S + (o, (1a)) where M is (D with a = (2( Tog(1 (1.25/8)/
We stress that the goal here is to demonstrate that the data value scores can indeed serve as another channel of privacy leakage. We do not claim any optimality of the attack we construct here. Improving MI attacks for data valuation is interesting future work.
5

---

Challenges in making KNN-Shapley being differentially private (overview). Here, we give an overview of the inherent difficulties in making the KNN-Shapley < differentially private, and we provide more detailed discussion in Appendix B.3 (1) Large global
(Theorem 2) to be
sensitivity: In Appendix B.3 we show that the global sensitivity of 22.0 (D- can significantly
exceed the magnitude of X: Moreover, we prove that the global sensitivity bound cannot be further improved by constructing specific pair of neighboring datasets that matches the bound. Hence, we introduce random noise proportional to the global sensitivity bound, the resulting privatized data value score could substantially deviate from its non-private counterpart, thereby compromising the utility of the privatized data value scores. (2) Computational challenges in incorporating privacy amplification by subsampling: "Privacy amplification by subsampling" [4] is a technique where the subsampling of a dataset amplifies the privacy guarantees due to the reduced probability of an individual's ss data being included. Being able to incorporate such a technique is often important for achieving a decent privacy-utilit tradeoff.. However, in Appendix B.3 we show that the recursive nature of KNN- Shapley computation causes a significant increase in computational demand compared to non- non-private KNN-Shapley.
These challenges underscore the pressing need for new data valuation techniques that retain the efficacy and computational efficiency of KNN-Shapley, while being amenable to privatization.
4 The Shapley Value for Threshold-based Nearest Neighbor
Considering the privacy concerns and privatization challenges associated with the original KNN- Shapley method, we introduce TKNN-Shapley privacy-friendly alternative of KNN-Shapley which also achieves improved computational efficiency. At the core of this novel method is Threshold-KNN (TKNN) classifier, simple variant of the KNN classifier. We will discuss how to incorporate DP for TKNN-Shapley in Section
4.1 Threshold-basee Nearest Neighbor Classifier (TKNN)
Threshold (TKNN) 5 72 is variant of KNN classifier that considers neighbors within a pre-specified threshold of the query example, rather than exclusively focusing on the exact K nearest
neighbors. Formally, for a training set S and a validation data point z(val) = (z((vl), y(val)), ) we denote NB gBg (S) ;= {Iz, (z, 3) E S, d,r (0(22)(()))) (v(a))) < J the set of neighbors of (vva)) in S within pre- specified threshold T. Similar to the utility function for KNN, we define the utility function for TKNN classifier when using validation set (vval) the aggregated prediction accuracy TTOY
e (Vva)))
(S)= ==
Extvali g (ival) ((val) (5) where
Constant
NB (val), , (S) =0 0
TRUE 2 (MHL)
(S)
Σ (x.g)emB (000), (9) [ly = y(val)]
NB _B_ (va) , (())
> 0
(3)
NB
(val)) (8)
where Constant can be the trivial accuracy of random guess.
Comparison with standard KNN. (1) Robustness to outliers. Compared with KNN, TKNN is better equipped to deal with prediction phase outliers [5). When predicting an outlier that is far from the entire training set, TKNN prevents the influence of distant, potentially irrelevant neighbors, leading to a more reliable prediction score for outliers. better computational efficiency compared to KNN, as it has O(N) instead of O(N log N) inference time. This improvement is achieved because TKNN only requires the computation of neighbors within the threshold r, rather than searching for the exact K nearest neighbors (3) TKNN is also consistent estimator. The consistency of standard KNN is a well-known theoretical result (26). That is, for any target function that satisfies certain regularity conditions, KNN binary classifier/regressor is guaranteed to converge to the target function as the size of the training set grows to infinite. In Appendix C.T. we derived similar consistency result for TKNN binary classffier/rerresoor.
(2) Inference Efficiency. TKNN has slightly
Remark 3 (Intuition: Why we consider TKNN?). The 'recursive form' of KNN Sha-llap due to the sorting operation in the prediction of the standard KNN. The recursive form of the formula causes difficulties in incorporating INN-Shapley with differential privucy. In contrast, TKNN avoids the recursive formula for its Data Shapley value; the intuition is that for TKNN, the selection of neighbors for prediction solely depends on the queried example and the validation data, and is independent of the other training data points.

---

4.2 Data Shapley for TKNN (TKNN-Shapley)
With the introduction of TKNN classifier and its utility function, we now present our main result, the closed-form, efficiently computable Data Shapley formula for the TKNN classifier.
Theorem 5 TTKNN-Shaplee (simplified version)). Consider the utility function v (2(va)) in 3 Given a validation data point 2 = (z<(vl), y y and a distance metric d(.,)), ) the Shapley value " of each training point 2 = (Iz. Ui) E D corresponding to utility function v soaa can be calculated as
$ TANN = (C2tsal) (D-zi)
(4)
where Cy(val) == (c, Cy(val), S(val) , is 3-dimensional fanction/vector s.t.
(+)
c= c(D == D
(size of D D=2,)
Crival),r = (y(vl)) i5 (D=zz) == 1 + 2 ,r (D-z:)
(1 + # neighbors of xf in D D=
(2(va)), so(va), ff (D=si)
(+) (+)
Σ
11y- - y(val)
(# same-label neighbors in D D=x.)
(x. (vaa)) (D-x.)
and f()) is a function whose exact form can be found in Appendix C.2
Runtime: the computation of all (0T, C.2.7J
TENN
(788
can be achieved in O(N) runtime (see Appendix
The Shapley value when using full validation set: The Shapley value corresponding to the utility function oi can be calculated as THBS (UTTER))
D(vaa)) ( DDvol Th (v: (val))
The main technical challenges of proving Theorem 5 lies in showing Cz(val) = (c. Cz (vo0)) >
three simple counting queries on D= are the key quantities for computing @ In later part of the paper, we will often view TTKN as a function of Cy(sal) and denote TTT [Cytvan] == f ((C,(va)) ) when we want to stress this dependency. The full version and the proof for TKNN-Shapley can be found in Appendix C | Here, we briefly discuss why TKNN-Shapley can achieve O(N) runtime in total. Efficient Computation of TKNN-Shapley, As we can see, all of the quantities in C_(va)) are simply counting queries on D and hence Cztsat) ( (D=...) can be computed in O(N) runtime for any 2, E D. A more efficient way to compute Cutvan (D=2.) ) for all 2; E D, however, is to first compute Cztsat (D)
the full dataset D, and can easily show that each of Cz (D can be computed from that in (1)) runtime (see Appendix CC2222 for details). Hence, we can compute TKNN-Shapley (DO
(u (v())) ) for all 2₁ E D within an overall computational cost of O(N).
Comparison with KNN-Shapley. TKNN-Shapley offers several advantages over the original KNN- Shapley. (1) Non-recursive: In contrast the KNN-Shapley formula (Theorem 2). which is recursive, TKNN-Shaples has an explicit formula for computing the Shapley value of every point 2,. This non-recursive nature not only simplifies the implementation. but also makes it straightforward to incorporate techniques like subsampling.
(2) Computational efficiency: TKNN-Shapley has O(N) runtime in total, which is better than the O(N log N) runtime for KNN-Shapley.
5 Differentially Private TKNN-Shapley
Having established TKNN-Shapley an alternative to KNN-Shapley which shares many advantages, our next step is to develop new version of TKNN-Shppley that incorporates differential privacy. In this section, we introduce our proposed Differentially Private TKNN-Shapley TOP--NNN-Shapley).
5.1 Differentially private release of
&
TRUM
TKKN g(val)
As Czivat) = (c, Cy(val), , (vaa)) )) are the only quantities that depend on the dataset D-2, in 64, privatizing these quantities is sufficient for overall privacy preservation, as DP guarantee is pre-
(+)
(+) served under any post protesrocsssing [6].. Since all of c, Cy(s)), and c 20m0),, are just counting queries, the function of Cz(sat) (-) has global sensitivity v/ f2-norm. This allows us to apply the com- monly used Gaussian mechanism (Theorem 4) to release Cytvat; in differentially private way, i.e., Czecals (D=.,) == round (Cz(van) (D_.,) N (0, o²1a)) where Cutwa) the privatized version of Czivaty and the function round rounds each entry of noisy value to the nearest integer. The differen- tially private version of TKNN-Shapler value TTEEE (D= is simply the value score computed by
7

---

but use the privatized quantities Czvan.. The privacy guarantee of releasing DP- SEETKKNN-haplAa
(D- follows from the guarantee of Gaussian mechanism (see Appendix D.1 for proof).
Theorem 6. For any z(val) E D(val), releasing TI. owner i is (e, 6DD with = v33 1/33.v/o//// (105(..//0))ee
(u 2((a)))) == 62.0 [C2cma (D (D-
to data
While approach may seem simple, stress that simplicity is appreciated in DP as complex mechanisms pose challenges for correct implementation and auditing [47
5.2 Advantages of DP-TKNN-Shapley (Overview)
We give an overview (detailed in Appendix D.2) of several advantages of DP- DP-KNN-Shaples here, including the efficiency, collusion resistance, and simplicity in incorporating subsampling.
By reusing privatized statistics, @ can be efficiently computed for all 2; E D. Recall that in
practical data valuation scenarios, it is often desirable to compute the data value scores for all of
2 E D. As we detailed in Section 4.2 for TKNN- such a computation only requires O(N) runtime in total if we first compute C (vvan (D) and subsequently Ca(van) (D=s,) for each 2j E D. In
a similar vein, we can efficiently compute the DP variant TTKNN for all 2; E D. To do so, we first P2 calculate Cg and then, for each 2; D, we compute Cz(mm)) (D=s.). It is important note that when releasing o%. to individual i, the data point they hold, 24, is not private to the individual themselves. Therefore, long as Caivat) (D) is privatized, Cz(.at) (D_..) and hence Trkn also satisfy the same privacy guarantee due to DP's post-processing property.
By reusing privatized statistics, DP-KKNN-shapley is collusion resistance. In Section 5.1 we consider the single Shapley value TXNX 2 (D-z) as the function to privatize. However, when we consider the release of all Shapley values ( ...... (TRMN) unified mechanism, one show that such a mechanism satisfies joint differential privacy (JDP) 34 if we reuse the privatized statistic
Cyoeaty (D) for the release of all T The consequence of satisfying JDP is that our mechanism is resilient against collusion among groups of individuals without any privacy degradation. That is, even an arbitrary group of individuals in [N] colludes (i.e., shares their respective Trewn values within the group), the privacy of individual remains uncompromised. Our method also stands resilient in scenarios where powerful adversary sends multiple data points and receives multiple value scores.
Incorporating Privacy Amplification by Subsampling. In contrast to KNN- HEN-Shapley, the non- recursive nature of DP-TKNN-Shaee Shapley allows for the straightforward incorporation of subsampling. Besides the privacy guarantee, subsampling also significantly boosts the computational efficiency of OP-TKNN-Shaples
5.3 Differentially private release of & (v)
TKKM (
Recall that the TKNN-Shapley corresponding to the full validation set (vval) is TXNN TKKK )
& @ Txam (D-zi i i (vva)).. We can compute privatized Φ (uTomm)) by simply releasing TTKNN (D-zi: 2 (val)) for all 2vall) (vval) To better keep track of the privacy cost, use the current state-of-the-art privacy accounting technique based on the notion of the Privacy Loss Random Variable (PRV) [7]]. We provide more details about the background of privacy accounting in Appendix [D.3 We note that PRV-based privacy accountant computes the privacy loss numerically, and hence the final privacy loss has no closed-form expressions.
6 Numerical Experiments
In this section, we systematically evaluate the practical effectiveness of our proposed TKNN-Shapley
method. Our evaluation aims to demonstrate the following points: (1) TKNN- offers im- proved runtime efficiency compared with KNN-Shapley. (2) The differentially private version of TKNN-Shapley (KP-T (DP--kNN-hhapley) achieves significantly better privacy-utility tradeoff compared to naively privatized KNN-Shapley in discerning data quality. (3) Non-private TKNN- Shapley maintains a comparable performance to the original KNN-Shapley. These observations highlight TKNN-Shapley's 's potential for data valuation in real-life applications. Detailed settings for our experiments are provided in Appendix E
8

---

maintains a high Remark 4. Given that differential privacy offers a provable guarantee against any potential adver- saries, our experiments prioritize evaluating the utility of DP-TKNN- ShaNley rather than its privacy properties. However, for readers interested in understanding the efficacy of DP in safeguarding training data, we have included an evaluation of the proposed MI attack on OP-TKNN-Shapen Appendix B.2.2 where it shows a significant drop in attack performance compared to non-DP version.
in
6.1 Computational Efficiency
We evaluate the runtime efficiency of TKNN-Shapley in comparison to KNN-Shapley (see Appendix E.2 for de- tails as well as more experiments). We choose a range of training data sizes N, and compare the runtime of
150
KNN-Shapley
Runtime (In seconds)
TKNN-Shapley
100
both methods at each N. As demonstrated in Figure [ TKNN LENN-Shapley achieves better computational efficiency than KNN- KNN-Shapley across all training data sizes. In par-
ticular, TKNN-Shapley is around 30% faster than KNN-
Shapley for large N. This shows the computational advan-
0-
tage of TKNN- Shaplee mentioned in Section 4.2
50000 100000 150000 200000 Training Data Points
Figure 2: Runtime comparison of TKNN-Shapley and KNN-Shapley across various training data sizes N. The plot shows the average runtime based 5 independent runs. Experi- ments were conducted with an AMD 64-Core CPU Processor.
6.2 Discerning Data Quality
In this section, we evaluate the performance of both DP and non-DP version of TKNN-Shaple in discerning data quality. Tasks: We evaluate the performance of TKNN- Shapley on two standard tasks: mislabeled data detection and noisy data detection, which are tasks that are often used for evaluating the performance of data valuation tech- niques in prior works [39 60). Since mislabeled/noisy data often negatively affect the model performance, it is desirable assign low values these data points. In the experiment of misla- beled (or noisy) data detection, we randomly choose 10% of the data points and flip their labels (or add strong noise their features). Datasets: We conduct our experiments
diverse set of 13
datasets, where 1l of them have been used in previous data valuation studies 33 60). Additionally. we experiment on NLP datasets (AG News [65] and DBPedia (2) that have been rarely used in the past due to their high-dimension nature and the significant computational resources required. Settings& Hyperparameters of IKNN-/KNN-Shapll
for both SONNNKKNN-hhaplee we use the popular cosine distance as the distance measure [53]. which is always bounded in [-1.+1] +1]. Throughout all experiments, we use 7 -0.5 and K = 5 for TKNN-/KNN-SSan Shapley, respectively, as we found the two choices consistently work well across all datasets. We conduct ablation studies on the choice of hyperparameters in Appendix E
6.2.1 Experiment for Private Setting
Baselines; (1) DP-KNN-Shapley without subsampling. Recall from Section 3.1 the original KNN-Shapley has a large global sensitivity. Nevertheless, we can still use Gaussian mechanism to privatize it based on its global sensitivity bound. We call this approach as DP-KNN-Shapley, (2) DP-KNN-Shapley with subsampling. Recall from Section 3.1 it is computationally expensive to incorporate subsampling techniques for DP-KNN-Shapley (detailed in Appendix [B.3.2). For instance, subsampled time compared with non-subsampled counterpart. Nevertheless, we still compare with subsampled OP-KNN-Shaple for completeness. These two baselines are detailed in Appendix B.4 We also note that an unpublished manuscript [67] proposed DP version of Data Shapley. However, their DP guarantee requires hard-to-verify assumption of uniform stability (see Appendix A). Hence, we do not compare with [67]. We evaluate the urivicy-utility tradeoff of DP-TKNN-Shapp Shapley. Specifically, for fixed 8, we examine the AUROC of mislabeled/noossy data detection tasks at different values of e, where & is adjusted by changing the magnitude of Gaussian noise. In the experiment, we set the subsampling rate q = 0.01 for TKNN-Shapley and subsampled KNN-Shapley. Table 2 shows the results on datasets, and we defer the results for the rest of 10 datasets to Appendix F.3.2 As we can see, DP-NKNN-Shapley shows a substantially better privacy-utility tradeoff compared to both DP-KNN-Shapley with/without subsampling, In particular,
Shapley with subsampling rate q = 0.01 generally takes 30 30nlonger
Results:

---

Mislabeled Data Defertion
Noisy Data Defection
DP-KNN-Shupley Shhppley (no subsumpling
DP-TKNN-Shaple
DP-KNN-Shapeey (no sabsampling)
DP-KNN-Shaplccy
Dataset
(ours)
(with subcompingg
(ours)
(with subsumpling)
0,1
0.883 (0.017)
0.49 (0.024)
0.733 (0.011)
0.692 (0.014)
0.494 (0,025)
0.615 (0.01)
2dPlumes
0,5
0.912 (0.009)
0,488 (0.022)
0.815 (0.006)
0,706 (0.004)
0.494 (0.012)
0.66 (0.004)
(0.009)
0.504 (0.019)
0.821 (0.005)
0.705 (0.007)
0.495 (0.011)
0.665 (0.0041
0.1
0.816 (0.011)
0.5 (0.014)
0.692 (0.011)
0.648 (0.028)
0,475 (0.042)
0,566 (0.01)
Phoneme
0.5
0.826 (0. (0.007)
0.197 (0.01))
0.738 (0.003)
0,683 (0.014)
0.536 (0.033)
0,588 (0.001)
0.826 (0.0015)
0.466 (0.01)
0,741 (0.002)
0.685 (0.016)
0,494 (0,071)
0.59 (0,005)
0,932 (0,007)
0.49 (0.028)
0.881 (0.005)
(0.037)
(0,074)
0,709 (0.011)
CPU
0.5
0.946 (0.0044)
0.507 (0.029)
0.978 (0.002)
0.838 (070)
0.472 (0,922)
0.746 (0:003)
0.948 (0.0022)
0,512 (0.008)
0.931 (0.002)
0.839 (0.003)
0,455 (0,099)
0,748 (0.002)
Table 2: Privacy-utility tradeoff of DP-TKNN-Shapleey and DP-KNN-Shapley for mistabeled/noisy data detection task on datasets
(see Appendix 1E.3.2 for the results the rest of 10 datasets). We set d = 100 and show the AUROC at different privacy budgets E; the higher the AUROC is, the better the method is. We show the standard deviation of AUROC across independent runs in ().
AUROC even when E = 0.1. The poor performance of DP DP-KNN-Shapley is due to its relatively high global sensitivity.
6.2.2 Experiment for Non-private Setting
Baselines; Our main baseline for comparison is KNN- KNN-Shapley. For completeness, also compare with other classic, yet much less efficient data valuation techniques, such as Data Shapley [23]. Data Banzhaf (60) and leave-one-out error (LOO) (55) Due space constraints, we only show the results for the famous Data Shapley here and defer other methods results to Appendix E.3.3
Results: We use AUROC as the performance metric on mislabeled/noisy data detection tasks. Due to space constraints, we defer the results for the task of noisy data detection to Appendix Table the results for the task of mis- labeled data detection across all 13 datasets we use. As we can see, TKNN-Shapler shows a comparable performance as KNN-Shapley across almost all datasets, demonstrating that TKNN-Shapley matches the effectiveness of KNN-Shapley in discerning data quality. More- over, KNN- -NN-leapley (and TKNN-Shapley has a significantly better performance compared to Data Shapley, which is consistent with the obser- vations in many existing studies [1 [22) The
Dataset
TKNN-Shapley
KNN-Shapley
Data Shapley
2dPlanes
0,919 (+0.006)
0.913
0.552
Phoneme
0.826 (-0.047)
0.873
0.525
CPU
0.946 (+0.014)
0.932
0,489
Fraud
0,96 (-0.007)
0.967
0,488
Creditcard
0.662 (+0.016)
0.646
0.517
Apsfail
0,958 (+0.01)
0.948
0.496
Click
0.572 (+0.004)
0.568
0.474
Wind
0,889 (-0.007)
0.896
0.469
Pol
0.871 (-0.057)
0.928
0,512
MNIST
0.962 (-0.012)
0.974
CIEARIO
0.957 (-0.034)
0.991
AG News
0.956 (-0.015)
0.971
DBPedia
0,981 (-0.01)
0.991
Table 3: AUROC scores of TKNNNKNNN-Sappleee
and Data Shapley for mislabeled data detection tasks on various datasets. The higher the AUROC score is, the better the method is. In the column for TKNN-Shaples we highlight its performance difference with KNN-Shapley in O. The results for Data Shapley on the last datasets are omitted due to computational constraints.
poor performance of Data Shapley is attributable to the sample inefficiency and stochasticity dur-
ing retraining (60).
7 Conclusion
In this work, we uncover the inherent privacy risks associated with data value scores and introduce TKNN-Shapley, a privacy-friendly alternative to the widely-used KNN-Shapley. We demonstrate that TKNN-Shapley outperforms KNN-Shapley in terms of computational efficiency, and is as good as discerning data quality. Moreover, the privatized version of TKNN-Shalley significantly surpasses the naively privatized KNN Shapley tasks such mislabeled data detection.
Future Work. (1) Privacy risks of data revelation to central server: in this work, we assume the existence of a trusted central server, and we do not consider the privacy risks associated with revealing individuals' data to the central server. Future work should consider integrating secure multi-party computation (MPC) techniques to mitigate this risk (59] MPC can allow the computation of KNN-Shapley without revealing individual data to the central server, thereby preserving privacy. We envision an end-to-end crivacy-preservinn data valuation framework that combines both DP and MPC. (2) Impact of Randomization on Payment Fairness: the incorporation of differential privacy necessarily adds degree of randomness to the data value scores. This randomization could potentially impact the fairness of payments to data providers [.. The influence of this randomness, and its potential implications for payment faimess, remain areas for further investigation.
10

---

Acknowledgments
This work was supported in part by the National Science Foundation under grants CNS-2131938, CNS- 1553437, CNS-1704106 CNS-2048091, IIS-2312794, ISS-2313100 OAC-2239622, the ARL's Army Artificial Intelligence Innovation Institute (A212), the Office of Naval Research Young Investigator Award, the Army Research Office Young Investigator Prize, Schmidt DataX award, Princeton E- ffiliates Award, Amazon-Virginia Tech Initiative in Efficient and Robust Machine Learning, the Commonwealth Cyber Initiative, Google PhD Fellowship, and Princeton's Gordon Y. S. Wu Fellowship. We are grateful to anonymous reviewers at NeurlPS for their valuable feedback.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pages 308-318, 2016.
[2] Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. Dbpedia: A nucleus for web of open data. In The Semantic Web: 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007+ ASWC 2007, Busan, Korea, November 11-15, 2007. Proceedings, pages 722-735. Springer, 2007.
[3] Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. Advances in neural information processing systems, 32, 2019.
[4] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems, 31, 2018.
[5] Jon Bentley. Survey of techniques for fixed radius near neighbor searching. Technical report, Stanford Linear Accelerator Center, CaliA, 1975.
[6] Yatao Bian, Yu Rong, Tingyang Xu, Jiaxiang Wu, Andreas Krause, and Junzhou Huang. Energy- based learning for cooperative games, with applications to valuation problems in machine learning. arXiv preprint wtt.:2/00.222.... 2021.
[7] Mark Alexander Burgess and Archie Chapman. Approximating the shapley value using stratified empirical bernstein sampling. In IJCAI, pages 73-81, 2021.
[8] Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song. Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pages 1914-1914. IEEE, 2022.
[9] Christie Courtnage and Evgueni Smirnov. Shapley-value data valuation for semi-supervised learning. In Discovery Science: 24th International Conference, DS 2021, Halifax, NS, Canada, October 11-13, 2021, Proceedings 24, pages 90- Springer, 2021.
[10] Rachel Cummings, Hadi Elzayn, Emmanouil Pountourakis, Vasilis Gkatzelis, and Juba Ziani. Optimal data acquisition with pwive agents. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 210-224. IEEE, 2023.
[11] Andrea Dal Pozzolo, Olivier Caelen, Reid A Johnson, and Gianluca Bontempi. Calibrating probability with undersampling for unbalanced classification. In 2015 IEEE Symposium Series on Computational Intelligence, pages 159-166. IEEE, 2015.
[12] Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Proceedings of the twenty-second ACM STGMOD-SIGACT-SIIGA symposium Principles of database systems, pages 202-210, 2003.
[13] Pradeep Dubey, Abraham Neyman, and Robert James Weber. Value theory without efficiency. Mathematics of Operations Research, 6(1):122-128, 1981.

---

[14] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology- EUROCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petershurg, Russia, May 28-June 1, 2006. Proceedings 25, pages 486-503. Springer, 2006.
[15] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[16] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- tions and Trends@ in Theoretical Computer Science, 9(3 4):211 1- 1-407, 2014.
[17] Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. CoRR, abs/ 1033/1673.01877 2016.
[18] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 5 Annual Symposium on Foundations of Computer Science, pages 51-60. IEEE, 2010.
[19] Cynthia Dwork, Adam Smith, Thomas Steinke, and Jonathan Ullman. Exposed! survey of attacks on private data. Anmual Review of Statistics and Its Application, 1:61-84,77 2017.
[20] Alireza Fallah, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar. Optimal and differentially private data acquisition: Central and local mechanisms. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 1141-1141, 2022.
[21] Marco Gaboardi, Michael Hay, and Salil Vadhan. A programming framework for opendp. Manuscript, May, 2020.
[22] Amirata Ghorbani, Michael Kim, and James Zou. A distributional framework for data valuation. In International Conference on Machine Learning, pages 3535-3544. PMLR, 2020.
[23] Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In International Conference on Machine Learning, pages 2242-2251. PMLR, 2019,
[24] Amirata Ghorbani, James Zou, and Andre Esteva. Data shapley valuation for efficient batch active learning. In 2022 56th Asilomar Conference on Signals, Systems, and Computers, pages 1456-1462. IEEE, 2022.
[25] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 164116633-16422 2021.
[26] Lászłó Györfi, Michael Köhler, Adam Krzyžak, and Harro Walk. A distribution-free theory of nonparametric regression, volume 1. Springer, 2002.
[27] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[28] Ferenc IlIés and Péter Kerényi. Estimation of the shapley value by ergodic sampling. arXiv preprint arXiv:1906 05224, 2019.
[29] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas Spanos, and Dawn Song. Efficient task-specific data valuation for nearest neighbor algorithms. Proceedings of the VLDB Endowment, 2019.
[30] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas Spanos. Towards efficient data valuation based on the shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1167-1176. PMLR, 2019.
[31] Ruoxi Jia, Fan Wu, Xuehui Sun, Jiacen Xu, David Dao, Bhavya Kailkhura, Ce Zhang, Bo Li, and Dawn Song. Scalability vs. utility: Do we have to sacrifice one for the other in data importance quantification? In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 8247, 2021.
12

---

[32] Justin Kang, Ramtin Pedarsani, and Kannan Ramchandran. The fair value of data under heterogeneous privacy constraints. arXiv preprint arXiv:2301.13336, 2023.
[33] Bojan Karlaš, David Dao, Matteo Interlandi, Bo Li, Sebastian Schelter, Wentao Wu, and Ce Zhang. Data debugging with shapley importance over end-to-end machine learning pipelines. arXiv preprini arXiv:2204.11133 2022.
[34] Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman. Mechanism design in large games: Incentives and privacy. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 403-410, 2014.
[35] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions.
In International Conference on Machine Learning, pages 1885-1894. PMLR, 2017.
[36] Antti Koskela and Antti Honkela. Computing differential privacy guarantees for heterogencous compositions using fft. CoRR, abs/2102. 12412, 2021.
[37] Antti Koskela, Joonas Jälkö, and Antri Honkela. Computing tight differential privacy guarantees using fft. In International Conference on Artificial Intelligence and Statistics, pages 2560-2569. PMLR, 2020.
[38] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[39] Yongchan Kwon and James Zou. Beta shapley: a unified and noise-reduced data valuation framework for machine learning. In International Conference on Artificial Intelligence and Statistics, pages 8780-8802. PMLR, 2022.
[40] Yongchan Kwon and James Zou. Data-oob: Out-of-bag estimate as simple and efficient data value. ICML, 2023.
[41] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist// 1998.
[42] Weixin Liang, Kai-Hui Liang, and Zhou Yu. Herald: An annotation efficient method to detect user disengagement in social conversations. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 3652-3665, 2021.
[43] Weixin Liang, James Zou, and Zhou Yu. Beyond user self-reported likert scale ratings: A comparison model for automatic dialog evaluation. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 1374-1374, 2020.
[44] Jinkun Lin, Anqi Zhang, Mathias Lécuyer, Jinyang Li, Aurojit Panda, and Siddhartha Sen. Measuring the effect of training data on deep learning predictions via randomized experiments. In International Conference on Machine Learning, pages 3346--13504 PMLR, 2022.
[45] Jinfei Liu, Jian Lou, Junxu Liu, Li Xiong, Jian Pei, and Jimeng Sun. Dealer: an end-to-end model marketplace with differential privacy. Proceedings of the VLDB Endowment, 14(6), 2021.
[46] Xinjian Luo, Yangfan Jiang, and Xiaokui Xiao. Feature inference attack on shapley values. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 2233-2247, 2022.
[47] Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. Proceedings of the VLDB Endowment, 10(6), 2017.
[48] Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. Sampling permutations for shapley value estimation. 2022.
[49] Arvind Narayanan and Vitaly Shmatikov. How to break anonymity of the netflix prize dataset. arXiv preprint cs/0610105, 2006.
13

---

[50] Ramin Okhrati and Aldo Lipani. A multilinear sampling algorithm to estimate shapley values. In 2020 25th International Conference on Pattern Recognition (ICPR), pages 7992-7999. IEEE, 2021.
[51] OpenAl. Planning for agi and beyond, 2023.
[52] 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 Health, Inference, and Learning, pages 2021.
[53] Sabita Rajbanshi. Chapter 1: K nearest neighbors (supervised machine learning algorithm), 2021.
[54] Nils Reimers and Iryna Gurevych. Sentence- bert: Sentence embeddings using siamese bert- networks. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019.
[55] Pierangela Samarati and Latanya Sweeney. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. 1998.
[56] Lloyd Shapley. A value for n-person games. Contributions the Theory of Games, 2(28):307-
317, 1953.
[57] Dongsub Shim, Zheda Mai, Jihwan Jeong, Scott Sanner, Hyunwoo Kim, and Jongseong Jang. Online class-incremental continual learning with adversarial shapley value. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9630-9638, 2021.
[58] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE sympostum on security and privacy (SP), pages 3-18. IEEE, 2017.
[59] Zhihua Tian, Jian Liu, Jingyu Li, Xinle Cao, Ruoxi Jia, and Kui Ren. Private data valuation and fair payment in data marketplaces. arXiv preprint arXiv:2210.08723, 2022.
[60] Jiachen T Wang and Ruoxi Jia. Data banzhaf: robust data valuation framework for machine learning. In International Conference Artificial Intelligence and Statistics, pages 6388-6421. PMLR, 2023.
[61] Jiachen T Wang and Ruoxi Jia. A note on" efficient task- data valuation for nearest neighbor algorithms". arXiv preprint 23X.:2234404225.. 2023.
[62] Jiachen T Wang and Ruoxi Jia. A note on" towards efficient data valuation based on the shapley value". arXiv preprint arXiv:2302. 11431, 2023.
[63] Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, and Dawn Song. A principled approach data valuation for federated learning. In Federated Learning, pages 153-167. Springer, 2020.
[64] Tianhao Wang, Yu Yang, and Ruoxi Jia. Improving cooperative game theory-based based data valuation via data utility learning. ICLR 2022 Workshop on Socially Responsible Machine Learning, 2022.
[65] Zhen Wang, Xu Shan, Xiangxie Zhang, and Jie Yang. N24news: new dataset for multimodal news classification. arXiv preprint arXiv:2108, 13327, 2021.
[66] Mark Wamer. Wamer& & hawley introduce bill to force social media companies to disclose how they are monetizing user data, 2019.
[67] Lauren Watson, Rayna Andreeva, Mao-Tsung Yang, and Rik Sarkar. Differentially private shapley values for data evaluation. arXiv preprint 2rXXi::200600511,, 2022.
[68] Cynthia Weiss. Mayo clinic platform: A patient's experience and beyond.
[69] Zhaoxuan Wu, Yao Shu, and Bryan Kian Hsiang Low. Davinz: Data valuation using deep neural networks at initialization. International Conference on Machine Learning, pages 24150-24176. PMLR. 2022.
14

---

[70] Andrew C Yao. Protocols for secure computations. In 23rd annual symposium on foundations of computer science (sfes 1982), pages 160-164. IEEE, 1982.
[71] I-Cheng Yeh and Che-hui Lien, The comparisons data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert systems with applications, 36(2):2473-246 2480, 2009.
[72] Yuqing Zhu, Xuandong Zhao, Chuan Guo, and Yu- Yu-Xiang Wang. Private prediction strikes back! Private kernelized nearest neighbors with individual Rényi filter. In Proceedings of the Thitty-Nimth Conference on Uncertainty in Artificial Intelligene, pages 2586-2596, 2023.
15

---

A Extended Related Work
KNN-Shapley & Its Applications. The Shapley value known for being computationally ex- pensive, Fortunately, (29] found that computing the Data Shapley for K-Nearest Neighbors (KNN), one of the most classic yet still popular ML algorithms, is surprisingly easy and efficient. To the best of our knowledge, unweighted KNN is the only commonly-used ML model for which the exact Data Shapley can be efficiently computed, referred to as "KNN-Shapley Owing to its superior computational efficiency and effectiveness in distinguishing data quality, KNN-Shapley has become one of the most popular and practical data valuation techniques. In the realm of MI. research, for instance, 14 extends KNN-Shapley to active learning, [57] employs it in continual learning setting, utilize KNN-Shapley for removing confusing samples in NLP applications, and [9] adopts KNN- WNN-Shapley for data valuation in semi- sunerisperei learning. Furthermore, KNN-Shaplee has also proven to be highly practical in real-life applications: [52 demonstrates that KNN- -NN--py is the only practical data valuation technique for valuing large amounts of healthcare data, and [33 builds the first data debugging system for andtto-end ML pipelines based on KNN-Shapley.
[43 42
Remark (KNN-Shapley vs General Data Shapley). In comparison to the work of general Data Shapley (23) (including Beta Shapley [39] as well as Data Banzhaf (600), KNN-Shapley may have the following differences: (I) KNN-Shapley focuses on KNN classifiers. As a result, the applicability of KNN- SNN-Shapley scores as proxy of data points' value with respect other ML models may not be straightforward. However, it is noteworthy that KNN is asymptotically Bayes optimal, implying that KNN-Shapley scores can be justified as a proxy for the data's 's value relative to the best possible model, i.e., the Bayes classifier, under certain asymptotic conditions. (2) For high-dimensional
data, such as images, KNN-Shapley requires public model to first map the original data into data embeddings, and evaluates the value of these embeddings rather than the original data. While this is indeed constraint in certain scenario, it is important recognize that utilizing a publicly available foundation model to convert original data into embeddings, febbeddigss.folowwddd by the fine-tuning of the model's ss last layer, has become a common practice. Therefore, in many situations, it might be more desirable to evaluate the value of data embeddings instead of the original data.
Privacy and Data Valuation. Few studies in the literature consider the privacy risks of data valuation. (59] explores a scenario where trusted server does not exist, and different data holders collaboratively compute each other's Shapley values without actually examining the data holder's data points, utilizing Multi-pane party Computation (MPC) techniques. The privacy risks addressed
in [59] are orthogonal to those in our paper, and we can combine both techniques for end-to-ue and-to-end privacy protection. Another orthogonal line of works 445 20 platform collecting private data from privacy-aware agents and offering a differentially private statistic computed from the submitted data as a service in return. Agents consider the privacy costs and benefits of obtaining the statistic when deciding whether to participate and reveal their data truthfully. 46) proposes a privacy attack on the Shapley value for feature attribution, while in this work we study the privacy risks when using the Shapley value for data valuation.
10 32] studies the scenario of a central
The unpublished manuscript by [67 is the work most closely related to ours. 67 explores how to make the Shapley values of data point be differentially private against the rest of the dataset. However, instead of focusing on KNN-Shapley, they study the privatization of the less practical, retrain-based Data Shapley [33 30 Furthermore, their algorithm is highly restrictive in that the differential privacy guarantee relies on the "uniform stability" assumption, which is not verifiable for modern learning algorithms such as neural networks. Moreover, while (67] argues the "uniform stability" assumption holds for Logistic regression on bounded data domain, it is unclear whether the uniform stability assumption still holds when the Logistic regression is trained by SGD (which may in- volve training stochasticity and early stopping). In addition, [67] does not release the implementation. Hence, in our experiment, we do not compare with it.
Remark 6 (Brief background for the privacy risks in releasing aggregated statistics). Since 1998,
researchers have observed that a lot of seemingly benevolent aggregate statistics of a dataset can be used to reveal sensitive information about individuals (55)). A classic example is Netflix Prize fiasco, where the researchers show that an anonymized dataset can leak many sensitive information about individuals (49). Dinur and Nissim [22 proved that "revealing too many statistics too accurately leads to duta privacy breuch". A great amount of discussion and practical realization of these privacy attacks on aggregated statistics can be found in [T9. 2020, the US Census Bureau used these privacy attacks to justify its use of differential privacy.
16

---

KNN- KNN-Shapley score for an individual is one kind of aggregated statistic that depends on the rest of the dataset. Hence, KNN- KNN-Shapley score intrinsically reveals private information about the rest of the dataset (where we use membership inference attack as a concrete example in our paper). In addition, when users collude, their KNN-shapley values can combined make joint inferences about the rest of the dataset.
17

---

B Details about KNN-Shapley, its Privacy Risks & Challenges of Privatization
B.1 Full version of KNN-Shapley
KNN-Shapley was originally proposed in (99 and was later refined in 61]. Specifically, [61
considers the KNN's utility function formula we present in the main text. Here the main result
of [61::
Theorem 7 SKNN-Shapley [61]). Consider the utility function in 22. Given a validation data point 2(val) (ax(val), yvva)) and a distance metric d(..-). ). if we sort the training set D {2,
(I -= according to d(x,, vlva)) in ascending order, then the Shapley value of each data point 6thh corresponding utility function A can be computed recursively as follows:
1[N 2 2|
1[yN = =y (mall)
1ly. = y(val)
min(K,N K.N)-
1 N
(LIw = // y =)
+
N
s+1
1ly: y(val)] 1/y+11 y(mi)
(in((K,))
1[ 2 K]
(min(i, K) (N K) x)
02441 +
Σ
N
K
where C denotes the number of classes for the classification task.
B.1.1 Older version of KNN-Shapley from 29
Prior to the current formulation of KNN-Shhpley introduced by 161. 29
proposed older version
of the algorithm. There is only a small distinction between the updated version by [61] and the older
version from [29]. Specifically, the difference between the versions proposed by [6]] and [29] lies in
the utility function considered when computing the Shapley value. [61 use the utility function (2) as
presented in the main text, while the utility function used in [29] is slightly less interpretable:
min( K. (S)
KIR-OLD (5) = K
Σ
1 (1 = -y (val))
(5)
(Val))
That is, (2) in the maintext divides the number correct predictions by min(K, [S]), which can be interpreted as the likelihood of the soft-label KNN classifier predicting the correct label yvval) for (vval), On the other hand, the function above (5) divides the number of correct predictions by K,
which is less interpretable when |S| K.
Nevertheless, the main result in 29 shows the following:
Theorem 8 (Older Version of KNN- from (29 Consider the utility function in 5 Given
validation data point (vva)) = (vvl)))), (vvl)) and distance metric d(.,-), if we sort the training set y/) ) according to d(x,, (val)) in ascending order, then the Shapley value of each
D = { = (1) data point ANH--OLD corresponding to utility function w KHR-OLD can be computed recursively as follows:
2(oa))
JyN Dval]
max K, N)
[ yvail 1[yet1 = Bvail min (K, i)
KNN-OLD
KBN-OLD
K
As we can see, both versions of KNN-Shapley have recursive forms. Since the utility functions they consider very similar each other except for the normalization term for small subsets, the two versions of KNN-Shapley have very close value scores in practice and as shown in the experiments of (61, the two versions of KNN-Shapley perform very similarly.
Remark 7 (The use of older version of KNN-Shapler for DP-related experiments). In the experiments, we use the more advanced version of the KNN-Shaph from [67] except for the DP- related experiments. This is because the global sensitivity of KNN-Shapley is difficult to derive, and we can only derive the global sensitivity of the older version of KNN- ENN-Shapley from from
(29] (as we will
We state more generalized version which does not require N > K.
18

---

show in Appendix B.3 Hence, we can only use the older version of KNN-Shapley from [29] as the baseline DP-related experiments. performance of KNN- INN-Shupley and its older variant is very close to each other, and which version of the KNN-Shapley we use for non-DP experiments does not affect the final conclusion.
important to note that for non-DP DP experiments, the
B.2
Settings & Additional Experiments for Privacy Risks for KNN-Shapley
B.2.1
Experiment for the changes of data value after eliminating nearby points
We first investigate the impact of removing a data point on the KNN-Shapley score of another data point that is close to the removed one. Specifically, we calculate the KNN- KNN-Shapley score for a chosen data point in the dataset, and then repeat the process after eliminating one of its nearby points from the dataset.
Settings. We use commonly used datasets in the past literature, and the details for data preprocessing can be found in Appendix [E.I] We calculate the KNN- Shapley score for randomly selected data point in the dataset, and then repeat the computation of the KNN-Shapley score after we eliminate its nearest neighbor from the dataset.
The results for a variety of other datasets are shown in Figure 3 We can see significant difference in the KNN-Shhpley score of the investigated data point depending on whether the nearest data point has been removed. We remark that how the data value change (increases or decreases) when the nearest data point excluded depends on the label of the nearest data point as well as the validation data being used.
Results.
dateset: traud
dataset: creditcard
dataset: apsfail
1.3
with the neartyy data point
without the nearby data point
1.06
(NN.Shapley
KNV Shapley
KNNV- Shapley
1.1
0.4
1.04
0.3
0.9
with the nearby data point
with neartyy point
without the nearthy data point
1.02
without the nearby data point
5
10
15
5
10
15
10
15
K
K
dataset: phoneme
dataset: click
dataset: wind
with the nearhy data point.
0.40
0.70
without nearty point
KNN Shapley
KNN- Shapley
IONN Shapley
0.35
0.65
0.30
1.0
0.25
with data point:
0.8
with the nearlyy data point
without the nearby data point
without cearby point
5
15
10
5
10
15
K
dataset: pol
dataset: 2dplanes
3.0
nearby point
0.50
KNN- Shapley 2
without the nearby data point
KNN- Shapley
2.5
with
0.48
without the neurby data point
2.0
1.5
0.46
1.0
5
10
10
K
Figure 3: Curves of KNN-Shapley of a fixed data point as a function of K (the hyperparameter for KNN), with and without particular nearby data point the training set.
For completeness, we also plot the same figures but for the older version of KNN-Shapley from 29 which shows similar results.
19

---

dataset: frand
dataset: crediteard
dataset: aps(ai]
1.3
0.5
with the neerby dasa poict
KNN Shapley
1.2
without the mearly point
JONN-Shaples
KNN-Shapley
1.06
1.1
0.4
1.0
1.04
0.3
0.9
0.8
witt: the neurby duta pount
without the nearny point
1.02
with the nearby data poict
wilkout the nearby data point
10
10
10
15
K
K
dataset: pheheme
dataset: click
detasett wind
144
withs usailly paint
0.40
0.70
without the tearby data point
KNN Shapley
KNN KNN Shapley
KNN- Shapley
1.2
0.35
0.65
0.30
0.60
with nearby point
0.6
with data
without the uearby dula point
without the tearby data point
10
15
5
K
K
dataset:
detaget: 2dplanes
3.0
nearbs data point
0.50
wilbout the neacby daia point
KNVN- Shapley
KNNN- Shppey
2.5
with Use nearby data point
0.48
without the nearby data point
2.0
1.0
15
10
K
Figure 4: Curves of KNN- -happlya (old version from (29) of fixed data point as function of K (the hyperparameter for KNN), with and without a particular nearby data point in the training set.
B.2.2 An Instantiation of Membership Inference Attack via Data Value Scores
The observation in Appendix B.2.T demonstrates the potential for KNN-Shapley scores to leak membership information of other data points in the dataset. To further demonstrate such privacy risk, in this section we show an example of privacy attack where an adversary could infer the presence/absence of certain data points in the dataset based on the variations in the shapllhapey scores, analogous to the classic membership inference attack on MI. model [58] The attack result further highlights the need for privacy protection when applying data valuation techniques.
Remark (Motivation of Membership Inference Attack), Membership inference attack, i.e., con- firming one's 's membership in database, could pose significant privacy risks. For example, if medical database is known to contain data from patients with specific conditions, this could disclose members' health status. We choose MI attack as our main example of the privacy risk as it has long been recognized as a fundamental privacy challenge across various domains, and such attacks have been extended well into the field of machine learning.
Remark 9. We stress that our goal here is the proof-of-concep where we demonstrate that the data value scores can indeed serve as another channel of privacy leakage, and can indeed lead to the design of membership inference allacks. We do not claim any optimality of the attack we construct here. Designing the best membership inference attack on data value scores can be the topic of single paper on its own, and is an interesting future work.
Our membership infer- ence attack technique leverages KNN-Shapley scores to detect the presence or absence of specific data points in a dataset. The design analogous to the membership inference attack against ML models via the likelihood ratio lest [ Threat model: The threat model we consider here is that the attacker can compute the value of any data point among any datasets (analogue to the setting of MIA against ML models where the attacker can train models on any datasets he/she constructs). Morcover,
Membership Inference Attack via KNN-Shapley Scores (Algorithm I.
20

---

Algorithm Membership Inference Attack via KNN-Shapley Scores. We collect data value scores of copy of the target example on datasets with and without the target example, estimate mean and variance of the loss distributions, and compute likelihood ratio test.
Require: dataset D, query example 2 = (z. y), data distribution Db.
1: KNNSV,
in = {
2: KNNSV = 0
3: for T times do
4: Dahadoo S TD // Sample a shadow dataset U2)) // collect IN data value 6: KNNSV in + KN U { (D // collect OUT data value
5: KNNSV in + iN U
7: end for
8: Min < mean iNNSV
9: Mout mean KNNSV out)
10: i + var(KNNSV, in)
11: Out var (KNNSV owt)
12: Oobs + Φ= // query target data value
pl NN (n) ))
13: Return p(oors
N (Houtt oun
the attacker can craft the data point it owns, send it to the server and obtain the data value score of its own data point.
The attack goes as follows: firstly, we create a shadow dataset D Shhadw by randomly sampling from the data distribution D. Dahudow serves as the function of D- in the maintext. We repeat this sampling process T times, where T is predefined number of iterations. For each iteration, we calculate the KNN-Shapley scores of a query example (IN) and when it is excluded (OUT). We thus collect sets of IN and OUT scores for the query example. Upon collecting all these scores, we calculate their respective mean and variance. Finally, we query the server about KNN-Shapley score of the query example = on the actual dataset D_ which we refer as the target data value (i.e., the server takes copy the target data point as the data holds. and send to the central server). We perform likelihood ratio test using the distributions of the IN and OUT scores. This test involves comparing the probability of the observed target data value given the Normal distribution of the IN scores with the probability of the same given the Normal distribution of the OUT scores.
(at, y) both when it is included in the shadow dataset
Intuition of the attack. The intuition of the attack is as follows: if the target data point is in the dataset, then if the attacker makes copy of the target data point and send it to the server, the server effectively has two exactly the same data point, which will result in a lower value of each data point. On the other hand, if the target data point is non-member, then the data value queried by the attacker will be higher.
For each dataset we experiment on, we select 200 data points (members) as the private dataset held by the central server. We pick another 200 data points which serve as non-members. Moreover, we leverage another 400 data points where we can subsample "shadow We set the number of shadow datasets we sample as 32.
Experiment Settings
dataset" in Algorithm]] I
Results on KNN-Shapley and TKNN-Shapley. Ta in the main paper shows the AUROC score of the attack results on KNN-Shapley. For completeness, additionally conducted the experiment of the proposed MIA against (non-private) TKNNNShapley and the results are shown in Table [4] As we can see, our MIA attack can achieve detection performance that is better than the random guess (0.5) for most of the settings. On some datasets, the attack performance can achieve > 0.7 AUROC. This demonstrates that privacy leakage in data value scores can indeed lead to non-trivial privacy attacks.
Results on -P-hple- To directly demonstrate how DP-TKNN-Shapley can mitigate the privacy risk, we additionally conducted the experiment of evaluating the proposed MI attack on OP-TKNN-SSaaple (see Tanle]5Jand[o). Compared with the result on non-private TKNN-Shapley, we can see that the overall attack performance drops to around 0.5 (the performance of random guess).
21

---

The result shows that SA-TKKN--Shllle is indeed very effective against membership inference attacks.
We stress again that the point of this experiment is not claiming that the membership inference attack that developed here is optimal MI attack data value scores; instead, this is proof-of-coneepl for the claim that data value scores can leak private information about other data points in the dataset, and instantiate possible privacy attack that exploits this privacy risks. We believe is interesting future work to improve the attack performance as well as explore other possible threat models.
0.9
0.3
0.7
0.6
==
0.5
0.4
7
0..3
0.2
7
0.1
DDPlanes
0.549
0.799
0.738
0.688
0,53
0.665
0.6
0.558
0.628
Phoneme
0.777
0.736
0.704
0.588
0.522
0.5
CPU
0.75
0.672
0.638
0.635
0.512
0.518
0.58
0.545
0.508
Fraud
0.752
0.529
0.577
0.594
0.558
0.715
0.678
0.7
0.645
Creditcard
0.55
0.501
0.664
0.685
0.59
0.56
0.597
0.552
0.52
Apsfail
0.506
0.529
0.608
0.574
0.558
0.507
0.569
0.571
0.526
Click
0.718
0.56
0.545
0.6
0.568
0.735
0.535
0.56
0.52
Wind
0,528
0.65
0.7
0.585
0.585
0.58
0.568
0,562
0.632
Pol
0.772
0.748
0.715
0.532
Table 4: Results of the AUROC of our MI attack on TKNN-Shapley.
=0.9
0.88
0055
-0.3
2DPlanes
0.51
0.474
0.488
0,518
0.494
0.51
0.479
0.466
0.478
Phoneme
0,502
0.505
0,512
0.506
0,5
0.484
0,552
0.538
0.482
CPU
0.468
0.489
0.486
0.51
0.523
0.524
0.468
0.466
0.527
Fraud
0.479
0.474
0,513
0.48
0,484
0,485
0,484
0,578
Creditcard
0.518
01495
0.511
0,522
0.501
0,483
0.448
0.521
0.535
Apsfall
0.484
0.476
0.471
0.492
0.486
0.5
0.493
0.434
0.454
Click
0.492
0.491
0,484
0,482
0.544
0.452
0.434
Wind
0.52
0.496
0,514
0,492
0.53
0,488
0.504
0.522
0.43
Pol 0.491
0.503
0.51
0.496
0.492
0.488
0.458
0.523
0.487
Table 5: Results of the AUROC of our MIA attack on DP-TKNN-Shaple (s 0.5).
0.9
f
T
T
T= 0.5
00.4
7
0.1
2DPlanes
0,523
0.513
0.534
0.492
0.484
0.445
Phoneme
0.507
0.529
0.524
0.472
0.476
0.488
0.543
0,512
0.47
CPU
0.492
0.487
0.504
0.485
0.473
0.489
0.453
0.49
0.508
Fraud
0.508
0.501
0.502
0.506
0.497
0.501
0.496
0.436
0.53
Creditcard
0.505
0.498
0.429
Apsfail
0.472
0.498
0.499
0.486
0.488
0.48
0.521
0.545
0.441
Click
0.502
0.529
0.501
0.508
0.518
0.496
0.545
0.47
0.456
Wind
0.533
0.539
0.478
0.504
0.493
0.498
0.529
0.499
0.419
Pol
0.498
0.513
0.509
0.51
0.482
0.492
0.489
0.52
0.528
Table 6: Results of the AUROC of our MIA attack on DP-TKNN-Shapley (s 1.0).
B.3
Challenges making KNN-Shapley being differentially private
In this section, give details of the inherent difficulties in making the KNN-Shapley KKN 2..,)) (i.e., Theorem to be differentially private.
B.3.1 Large global sensitivity
We find it very challenging to tightly bound the global sensitivity of 2 (D)..). Moreover, we show that the global sensitivity of JKHN (D-z.) can significantly exceed the magnitude of xom by showing a lower bound. Specifically, we prove that the global sensitivity bound at least around O(1) by constructing specific pair of neighboring datasets.
Theorem 9 (Lower Bound for the global sensitivity of (D=x)) For a data point (x, y) and validation data point (val) (va)) , (vva)),, denote the global sensitivity of (8 (val)) as
22

---

A 1 x(val)) = supp-,_D'_ ,nDL_, (D=s: -- (D'=:: ( We have
( ( -1
where the number of classes for the corresponding classification task.
Proof. The proof idea is to construct two neighboring datasets: D {22) D' f 22) where (21, v1), 2/2 (22,, y2) are two data points and we let 1/1 y Moreover, let 2val))))v))))) S d(z2, (vva))). From KNN-Shapleyss formula in Theorem we have
(D) = 1 1[322 = y (vll) 1/C #2
and if K 2 2, we have
1 4 [1882 = y (val)] 1/311 = =y((al)]) + 1 (1ly2 = -10)
2 (D') =
and if K 1, we have
X20 DD) 2 (1l82 = y(val)] - - 1/C)
2
Since 1 = y/(val]] (our condition), we have
1 y
KMN (D)
KKN (D')
2
The above theorem tells us that the global sensitivity for KNN-Shapley is at the order of O(1). On the other hand, we for many of the data points 2 is at the order of O(1/N). Hence, if we apply the Gaussian mechanism and add random noise proportional to the global sensitivity bound, the resulting privatized data value score could substantially deviate from its non-private counterpart, thereby compromising the utility of the privatized data value scores.
from the formula of KNN-Shapley in Theorem that the magnitude o
As we said earlier, hard to bound the global sensitivity for 6eTh Moreover, even if we able to bound the global sensitivity, the bound will highly likely be large compared with the magnitude of g as we can see from Theorem 9
Tight Global Sensitivity for the older version KNN-Shapley from 229
In order to find a reasonable baseline for comparing with DP-TKNN-Shapley, we consider the older version of the KNN-Shaple Shapley developed in (29), where show that its global sensitivity can be tightly bounded (but still large).
Theorem 10 (Global sensitivity of @EEN-OLD
For a data point z (xr, v) and validation data point (vaa)) (valv,), . (vval)), denote the global sensitivity of Φ ( (D_; (vvl)) as A N8w OLO, 2 (val)) ;= supp_,<D'_ 10 (ONN-DLD (D_ (val)) xxnu-
(D-:) from 29
OLD (D' (D'z; 2v(l))))) We have
A A ((all))
((val))
K(K +1
Proof. For any dataset D - D_ (2), we sort the data points according to the distance (val)) and denote zj for the jthh closest data point to (vaa)) WLOG, suppose 2; z. We first write the non-recursive expression for the older KNN-Shapley d KLNN
1 1 Vral]
[ Vval]
1 Wojt1 Dvail min(m,))
KUN-OLD
max N)
If N K, then have e
OLD
1/: my [val)
for all i (i.e., no privacy leakage in this case).
23

---

If N > K, there are two cases:
Case 1: i 2 K, then have
KKN-OLD
1 [1/ (val))
Σ
G - 1)j 1,y; y(val))
1
jmit1
Hence, if we add/remove a data point 2j = (Iz.. UUi) s.t. d(Iı, x(val)) 2 d(ar, x(vall),, we have
1
KNN-OLD (D=,,) - 62 Kun-OLD
(D'=x)1 (omm-oo(D'-z))
(j-1)} S K(K+1)
If we add data point 2j (0:j. Ub) s.t. d( (vaa)) d( (vall)) we have aam--OL OLD (D=
jKmn-OLD (D' 21
1 1111 = y [val)]
N
1lv = straly)
1lvi = y(val)]
Σ
N
11 10;
i
1}j
it1
- 1)j
jmi+1
jmi+2
( x+11
N
1ly = y(vall]
Σ
(+1)))
1lv; = y(aal]
(j-1)
j=i+1
1
i(i+1) 1) 1
K(K 1)
When 2 K + the sensitivity analysis for remove data point 2j (Ij, s.t. d(z,, x(val))
d(zii, x(aa)) is similar to the analysis above where we also have
XIR-OLD OLD
(D=,,)
XMB-OLD
(D'
(D',,)) 5
K K(K + 1)
Case 2: i < K, then we have
1 = (val))
N
KKX-OLD
1lus y
K
(j (j- 1)j
j=K+1
By similar analysis, we can also show that
KOR OLD (D-2.)
X0N- OLD (D'
DD=,,)] K(K +
The only remaining case that we haven't discussed yet is when = K, and we remove a data point 2j (2), s.t. d(æ,, (val)) < d(I, (vaa)). In this case, we have
1 x2mn-OLD (D 2.,))
JKNN-OLD ((mi- (D'=2.)
1 1l/ (val))
Σ
1
1 = y yvaal)]
1/ys (val)
Σ
(j 1)j 199 y(vall)
K
(j - 1)j
K
jm K+1
j
K+1
1
0 <
K(K +1)
We stress that the bound K(K+1) is tight. For example, for the case where i K, then if we add another data point 2" = (xx "0"","" s.t.
d(z,, d(oK, (val)) S d(z", (val)) & d(
the change of the value o -Ln-OLD will be K(K+I)
24

---

B.3.2 Difficulty (computational challenge) in incorporating subsampling technique
"Privacy amplification by subsampling" 4 is technique where the subsampling of dataset amplifies the privacy guarantees due the reduced probability of individual's data being included. Being able to incorporate such technique is often important for achieving decent privacy-utility tradeoff. However, the recursive nature KNN-Shapley computation makes it hard incorporate the subsampling techniques.
Specifically, recall that in practical data valuation scenarios, often desirable to compute the data value scores for all of 2 E D. To apply the subsampling technique, we first need to create subsampled dataset and compute the KNN-Shapley for the target data point 24 i.c. we need to compute de (sample e D D)=)). The subsampled dataset is usually constructed by sampling each data point independently with probability q (this is usually referred to as Poisson subsampling ). If
we view g as a constant, then the computation of dK (sample D-:)) requires a runtime of O(N)
for the computation of each daa This results in final runtime of (N2)) for the computation of all (d )..ED. which is a significant increase in computational demand compared to the non-private KNN-Shapley The recursive nature of KNN-Shapley computation significantly complicates the attempt of improving the computational efficiency. That is, it is not clear how to reuse the subsampled dataset to compute the KNN-Shapley score for those that are not sampled. Therefore, seems that an O(N2) runtime necessary if we want to incorporate the subsampling technique.
B.4 Baseline for experiments in Section 6.2.1
DP-KNN-Shapley. Given such an upper bound for the global sensitivity of Φ KKX-OLLD we can
Gaussian mechanism (Theorem 4 to privatize 2 i.e., we compute pynx-OLD/ (D=:) 2eth
OOND-LL (D=z)+ +N (o, K(K+T] We note that such a bound is still not satisfactory the magnitude
KEN-OLD for many of the data points is at the order of O(1/N). Nevertheless, this is reasonable 2
baseline (if not the only one) that we can use for comparison in DP-related experiments.
DP-KNN-Shapley with subsampling. Despite the high computational cost associated with the incorporation of the subsampling technique, we still compare our approach with this computa- tionally intensive baseline for completeness. More specifically, we compute @=
Jmm-OLD (D=z) =
KEX-OLD (sample(D-:) + / (., (N(O0.)x(x)
25

---

C Details for TKNN-Shapley
C.1 Consistency Result for TKNN
For a data point x and a threshold т, we denote
Se, == {x')d(z x²) S
the ball of radius r centered at æ, Recall that the prediction rule of TKNN when given training set D is
MB (D) =0 NB,,- >
mD (2;T)
[BBr,-(D)I Ex"ExB...()) m(x')
Theorem 11. Suppose m the target functionn that is Lipschitz on supp(u) where is the probability measure of data distribution. As n + cc, if 0 and ny((S2,7) + 00 for all x E supp(j(). then
lim Da [mm, (I)) m(x))²] = 20000
Proof.
Ex Bee.D.l(mp. (x) m
-.,,D, (mDD, (x) m(x))² [ (D.)) > Pr [ (Dn) 0)
a,
+ EZ.DD. [(0 m(x)) (D,)) = 0]
Pr
[NBr,,, (Da)l = -
r. D.D.
lim Pr [ (D,)) = = lim Eg
Pr [[NB (Dn)l =0]
n-000 D.D.
n-000
Dn
litn Ex
[(1 - p(S 1)=1
n=000
1
lim Ex
n=000
1 nis (S
Suppose m has Lipschitz constant L, i.e., for any pair of data points 2, x' E supp(u),, we have [m(xx) m²x')l L ||
z'll
En, [mm, (x) - NB,, (Dn)l > 0j
2 |NBB,,T, (Dx)
(0(()))(())
|NB (Dn)
E'ENB.. (Pm)
< Er.D..
(m(x') - m(x))² (Dx)l 0
NBe..r (Dn)
Z'ENB, (Dn)
< En,,.
(m(x') - (m))) (Dx)) >
NNB (Da)
z Z'ENB,,TA (D,)
< En
La || - 2'112 | (Dw)) >
|NBr.t. (Dr)
z'ENB, (Da)
< En
Σ
1.2721 [N (Dn))
[NBr,T. (D.)l
E'ENB,, (D.)
L2T2
which + 0 as 00.
26

---

C.2 Proofs for TKNN-Shapley
Given dataset S and test data point (ar(va)), ( S, d(x, (((a)) I h the nearest neighbor of (vaa) that within pre-specified threshold т. Recall that in this case, the utility function of soft-label TKNN classifier becomes
(fva))), let NB NBg(va),-(S) ((x, ()) (a,
1//C
NB (va)) ((S) = 0
uSS (x(val), ((va))))
NB (val),, (5]] E(r.))eN (vab) , (() 1yy = (vaa)
NB (vol)) ,7 (SS) >
where C is the number of classes for the classification task, and 1/C is the random guess accuracy. Semivalue. The class of data values that satisfy all the Shapley axioms except efficiency is called semivalues. was originally studied the field economics and recently proposed tackle the data valuation problem [39]. Unlike the Shapley value, semivalues are not unique. The following theorem by the seminal work of [13] shows that every semivalue of player z (in our case the player is a data point) can be expressed as the weighted average of marginal contributions v(S v(S) across different subsets S S N (z}.
Theorem 12 (Representation of Semivalue [13). value function Peemi is semivalue, if and only there exists a weight function w : [N] + R such that Ek (x-1) wokk N and the value function can be expressed as follows:
1 N
2z. (D=ziiU,w)
Σ
w(k
Σ
[z) =SS)
N
(6)
SCD
SCD-
Semivalues subsume both the Shapley value and the Banzhaf value with Wshap (k) = (ド-1)² and
Wbanz( (k) - respectively. In the following. we first discuss the general semivalue for soft-label TKNN classifier with a weight function w. We then plug in the specific weight function for the Shapley value.
Our goal to derive 02, (D=z,i w)) the semivalue of z; = (2i v:) with a weight function w when using soft-label TKNN classifier, i.e.,
22, (D=z,jU, U w)
w(k) Σ
[x(SU
SCD-1. 1
Consider validation data point (z(val), (val)), and recall that v(S) == v(S (z(val), (vall)). Denote
Ca(sal), C2(ival, (e ==
|B (uall (D=z.)
(1 + # neighbors of xf (val) in D=2,)
(20al),r ((vv)), (D_ (D=z.) :=
(+) c. (+)
Σ
1/y = (val))
(# same-label neighbors in D=z;)
(K, (val)
(val) (D-.))
Case 1: if || - x(val)||
> t, we have v(SUz) -v(S)= = for any S, hence dz, (D=..iu, w) = 0.
Case 2: if | - [vva)||
< we have the following:
v(S U 21) - v(S) =
(mm))
It NB [(v))) , [(T
+
I+ (val) (9)
MB (vall, (ST
(ST
Σ (z.z) EuB ,iva),, (8) 1ly Dvail
NB ( (S) > 0
1 [yy (val)) - 1/C²
NB (vvl)) (S) = 0
27

---

This means that the marginal contribution on S only depends on the subset NB ( S S. Plugging in the above equation for v(S U 24) v(S), we have
23 (D -z
U, w)
N-1
w(k +
(z()U(z)) (SS]
N
0=
SED 44 |S|=
N-1
(N.
N Cz((al),
w + 1)
E
[0(So (2i)) - v(So)
N
h - Sol
0=
So NB
2 (val), (D-a.)
180 Sk
N-1
(k + 1)
Σ
N - C2(val),7) h -
( - ((S))
N
K=
5=
MB
(val) (D-2,)
|
N-1
w k + 1)
k
Σ
N - Catan Ny it
[y = ((al))
+
[1+ (1
1
Σ
1lv -y-= = x
N
k j-j
1+j
0=
j=1 So XB
(val)
(D (D=..).
(x.g)ESo
|
(0)
N - Cx(val),
[1lv: y(vat)) (yvab)-1/C9) -1/|]
+
k
and
N Calvall,r it k - j
(Cotrall or -11 1) 1 [v: = (val))
1 (14s-1)
Σ
Σ
Σ
1 y(vall]
j
S. (vvl)) - (D-a,) (x.
1 |=]
5
(+)
Calval),+ - -1 (+) 2(vv))),
Σ Σ
1 (val))
Σd
l
2(val), v
j-
So CB (val) (D=.;) (2.0)ES,
|
i
(+)
1) 8-1
Cr(veN),, (+)
= c
2(val),
22(uu)),7
((val))
,7
j-6 l
E=1
= c((-)
Ca(val), - -2)
2(val), ,
j 5-1
28

---

Hence
N Cz(va)), i ) [
- 11 1 [bzi y(val))
+ c (+)
1+j 3) (
(2(oul),T 2 y -
}
k --1
j
1 j
2(m0)) ,f
j=l
1[c)(va)), 2 2]1[yi = y yvali)
Σ
N Cp
Czztral) i
1
k - j
1
(c(t) (+) =(val)),
Σ
N Czive),,
Cgr(val),T
2) j(i +
k j
j j-1
j=1
-1(r)(m)), 2 2]1l[r = y (valy)
N Cr(ial),77) k j
(zztual),r
1
1 + 1
Celvaa)
,7
(+) (+) -Cg(va)) it
N Cz(va),, o k-j
Cartval),r
1 [ccoivals, 2
j 1
Cy(mal), ,r (Colval),r
1)
1ly = y(val))
s(val),+
b
N Caivval)r
=1[cg(va),r 2]
Car(val),r o
Calvaa), or (Catvall, x
k
--1
j 1++1
j=1
=1(c 2]
1lyl = y(val))
(2(ol))
[
N
(N Calval),r
(N Cy(val)
(+1)
(v +
(vll)) o (ca))))),
1)
k+1
1B(1)
Hence,
1
N-1 Σ
1 = (val))
(+)
S3 (D-zi w)
w(k + 1)
I(Cg(ral, 2 2]
B(k)
N
Cy(val), ir
covvl)) (Carivals, 1)
k=
+ N -N--cooe Colval)
[ = y(val)) - 1/c|
k
[[cgive),r 21
1ly = (vaa))
(+)
2(v0l), ,
N-1 w(k 1)B(k)
N
Cy(xal),,
(val))) ,r (Cog(voal), 1)
k=
1
N-1
(N
NN Cx(va)),7
1l1i y(val)] 1/0
Σ
w(k 1)
N
C.2.1 The Shapley value for TKNN (TKNN-Shapley)
Theorem 13 (Full version of TKNN-Shapleyy). Consider the utility function 22(mm) in (3) Given a validation data point (vval) (vall,,,, yf ), the Shapley value TENE ( (Ii, U:) E D can be calculated as follows:
TNNE
TE of each training point
[(c 2 A/ + (
(( ST dax,, 20 (rall) (val)) >
7XMY
(7)
0
(())
a-2
where A
[val)))
(v(aa)) (c (v(aal),, - -1)- As = Ei=0
[val), r
1
(val))
- 1,
Ca(val),
k+1
k+1
cti
(_((a)))
29

---

and
c c=c(D=]) = 1 -2i
(size of D=z;)
Cg(vu)), = Cz(vo)),- (T) (1=x,) = + MB (val), (-( (D-
(1 + # neighhors of (val)) D=2.)
(4) = =c
= (D=z,):= ==
(4)
Σ
1 1yy yf mmlll
(# same-label neighbors in D D-
((va)),
(a. ((va)) (D_
and C is the number of classes for the classification task, and 1/C is the random guess accuracy.
Runtime: the computation of all ( 202
.....,I2
TxRN) can be achieved ONN) runtime total.
The Shapley value when using full validation set: The Shapley value corresponding to the utility
function u Divaly can be calculated as &z. THR
(u (( Σ E(tval) E Divaty 7E88 (ggina)) ).
Proof. For the Shapley value, we have wk:) = (x-1)
N wkk + 1)
N
N 1
1
N 11
(6
= Σ
k:
(1+1)
k
k
k++1)
k=0
N
Σ
k+1
k=0
N-1
(N-ce
(N - Caival),r -Cgivall) o k k+1
N
(N - Ca iT k k+1
((k + 1).
k
k
kN(N - 1 k)!
(N Cp
(N 1)!
(k+ 1)!(N - Caival),r k - 1}!
(N Cz(val), )
N-1
IN k:)!
(N 1)!
1: 1+1NN - Cz(val), - k - 1)!
k=0
(N Cy(va)), ,- ),,c
N-1
N - k6 k ++1 Cylival,rr
(N - 1)!
k=0
-1 -IN-1
N N
N - - k Cyi(va),r
C2(va),, ,5
k
Σ w(k + 1). (N- -C
N-1
Σ
N 1
N
Cg(iva)) ,r
k
k
k
K=
k=0
(N
Cy(val), ,r) )!
N-1
(N - 1 - ki)!
(N 1)!
(N Cy(val) if - 1:)!
k=0
N-
N-1
1-1 k
Cariva),r -
Catval),r -
K=
N
-1 N
Calvva),
1
Cz(val) ,
N
Ca(val),7
30

---

Φ2 (D-
11 C/ 2 2]
1ly = y(val)]
2(vul),7
N-1
Σ
N 1V-11
1)
-1
B(k)
N
Cuival), 7
Co(sal), (Ca(vxa)) if -1]
k
km
N-1
-1 - Cz(val), i7
N 1ly: = y(val)) - 1/c
k
A
k=
1((x(va)), 2 2] 1lye = yy(va))
c
2(val),
(+)
N-1
1
1
(N-1-k)
_((l)) ,r
1
Cofval),+ (Co(vvl), - 1)
1: +
1: +
1
k=
(val)
+ +[119: = - -1/C] C
1
-1( 22] 1ly = (val))
2(vel),r
(+)
1
c-k c (vall)
Cz(val),,
Calvval) (C2(val),, ,r 1)
k+1
A + 1
R=0
11y = y(vva)] - 1/c]
Caival),r
C.2.2 Efficient Computation of TKNN-Shapley
As see, all of the quantities that needed to compute TKNN-Shapley value (c, Cy(saa)), : c (+) 22(al)) ) are simply counting queries on D- and hence Cz(van) (D- can be com- puted in O(N) runtime for any E D. Since our goal is to release ( for all = E D. we need to compute Cg (D=z,) for all 2; E D. A more efficient way for this case is to first compute Calvan (D) on the full dataset D, and then we can compute each of Czival) (D-z.) by
c(--..) c(D)
Cyival), or (D-2,) = Cy(val), , (D) [[2 E NB (vvo))))..)) , (+)
(vaa)) (D=,,) 22(ml), (D) 1 [Ex NB ]1 [ys = (val)))
(+)
which can be computed in O(1) runtime. Hence, we can compute TKNN-Shapler 6TKNN ((ta)) ) for all 2; E within overall computational cost of O(N).
31

---

D Extra Details for DP-TKNN-Shapley
D.1 Privacy Guarantee for DP-TKNN-Shapley
Theorem 14 (Restatement of Theorem 6.. For any z!val) E D(val), releasing Traw (w =
TKNN
(D= to data owner i is (e, 6DD with = v Vlog(1 (og((125//)/e
Proof. The Gaussian mechanism is known satisfy (),D) with A v log( (1.25/0) 16.
where A := supp-D' (Df f(D))) represents the global sensitivity of the underlying function in le norm. In our case, f calculates the 3-dimensional vector c, Cy(m)) , 2(vx)), As each
(+)
training data point may alter both Cg(vaU,r and c(t) C20=)),r by 1, the sensitivity A v3. Since both
Cz and c(t) (2(w)), , are privatized using the Gaussian mechanism, the privacy guarantee of 62, is ensured by the post-processing property of differential privacy.
L
D.2
Advantages of DP-TKNN-Shapley
D.2.1
Computational Efficiency via Reusing Privatized Statistics
Recall that in practical data valuation scenarios, it is often desirable to compute the data value scores for all of 2, E D. As we detailed in Section 4.2 and Appendix C.2.2] for TKNN-Shapler such computation only requires O(N) runtime in total if we first compute Cztva (D) and subsequently Cztvat) D for each 2, D. In similar vein,
efficiently compute the DP variant TTKN
for all 24 E D. To do so, we first calculate Cyrvan (D) and then, for each E D, we compute Cycvat) (D_,,) follows:
ē(D-2.) ē(D) -
é (val)) (D = C,(l))), (D) 1[2g E NB (val))
(+) =((ul), (D=z,) = -c(+) (2(va)), (D) - 1[z NB ,t [1 = (val))
which can be computed in (1)) runtime. Hence, we compute OP-TKNN-Shaple T for all 2; D within an overall computational cost of O(N). It is important note that when releasing TKMM individual i, the data point they hold, 2;, not private to the individual themselves. Therefore, as long Cytva (D) is privatized, Cyrou)) (D=,,) and hence Tra also satisfy the same privacy guarantce due to DP's post-proces post-processing property.
D.2.2 Collusion Resistance via Reusing Privatized Statistics
In Section 5.1
we consider the single Shapley value T SD as the function to privatize. How-
ever, when consider the release of all Shapley values M(D) (a D_.z)...... T (D_ex) as a whole mechanism, one can show that such a mechanism satisfics joint differential privacy (JDP)
[34] if we reuse the privatized statistic Czevar (D) for the release of all TTEN The consequence of satisfying JDP is that our mechanism resilient against collusion among groups of individuals without any privacy degradation. That is, even if an arbitrary group of individuals in [N] \ colludes
(i.e.. shares their respective Trew values within the group), the privacy of individual i remains uncompromised. Our method also stands resilient in scenarios where powerful adversary sends multiple data points and receives multiple value scores.
Definition 15 (Joint Differential Privacy (34). ). For 2 a randomized algorithm M NX - V.N is (e, joint differentially private for every possible pair of 2, z' E for every i E [N), and for every subset of possible outputs E _ YN -1, we have
Pr(M(SUD-:) E
where M_, denotes the output of M that excludes the ith dimension.
32

---

Theorem 16. The mechanism of releasing of all noisy KNN- KNN-Shapley values
M(D) =
(D=
P ( (D-2x))
T
TERN satisfy (s,8)-JDP if = v3- vootoo:3/-/v////////oo /log(1.25//))) and each & 2 is computed via reusing the privatized Cz(sal).
Proof.
The proof relies on the "post-processing" property of differential privacy.
First of all, we select o = v3 Vlog(1.25//)) (12/5/) ensuring that Catval) (D) satisfies (s, 0)-DP.
In the context of DP-TKNN-shapley, we calculate Cycsany (D=2:) for each 2, as part of post- processing step Cycoa (D).
is important to note that the released data value @ (D-..) is a function of Czimn (D-.;) ) and Cycvan) (D=z,) can be obtained as post-processing of Cgtval) (D) given only the knowledge of z;. Hence, we can express the probability of M(z;, D- belonging to a certain set as follows:
D= D= E]
Pr [fD-., (C2cua)) (D)) E]
M
Č (ytaa, (D)
where
fD... C2roa (D))
TKIN (zivat) (D=.)).--...
TKEN CC (vea)) (D=z; M) Pxi1 (Cztvan (D (D= (D= Czivals (D
TRMN
TRN
We note that fD-.; is a function that does not depend on Zi.
Then, for any 2,, 2f and for any tuple D s. denote have
D=
2, 2,UD- and D' 24 U U-DD- we
(GM((,DD=2)-- M
Pr ifD_,, (2zmma) (D) E E]
č (vaa (D)
Pr
Cyrvals (D) $D (E)
(aa) (D)
Pr C (2(mm) (D') E fō_,, (E) +
I è (Dn)
c
Pr [fD_, (C_com) (D')) E +
e PriM(,, D_2, E) 5
where the first inequality is due to the 8)-8) guarantee of Crroal (D).
Hence, the privacy guarantee for our OP-TKNN-Shaple remains the same even if multiple attackers collude and share the received noisy data value scores with each other. As comparison, the naive OP-KNN-Shaple which independently adds noise for each released data value score does not enjoy such powerful collusion resistance property.
D.2.3 Privacy Amplification by Subsampling
In order to further boost the privacy guarantee, we incorporate the privacy amplification by sub- sampling technique []. Specifically, before any computation, we first sample each data point independently with a probability q (this is usually referred to as Poisson subsampling). The differ- entially private quantities based on the subsampled dataset, denoted as sample( (), calculated casily as follows:
a(D) == round (c(sample(D)) + +N +0. (0,
Calvall) ,r (D) = round (C,(ve)), (sampee ()) +W (0,
(sample(
((-) (2(va)), (D) (DD) = round (+)
_2(v))) (sample D)) +N (0.0²)
33

---

The function round rounds a noisy value to the nearest integer. If the noisy value is out of range (e.g., < 0), then it is rounded to the nearest possible value within the valid range. By subsampling the data points, the privacy guarantee is amplified. This is because the subsampling process itself is randomized operation that provides level of privacy, making harder to infer information about individual data points. When combined with the Gaussian mechanism, the overall privacy guarantee is improved.
The subsampling technique can be incorporated easily for DR-TKNN-Shapley as above, where the subsampling technique only improves the computational efficiency. As a comparison, incorporating subsampling technique for Pe--KNN-Shhpple will introduce significantly higher computational cost, as we discussed in Appendix BB..22
D.3 Differentially private release of oz.
TKNX (UTT Divaly)
(Privacy Accounting)
Recall that the TKNN-Shapley corresponding to the full validation set D is TKNN (1 =
Ezivalle Divall T (D=ze = z =(val)). ). We can compute privatized @I,TN (1 by simply releasing (D-2; 2 )(va)) for all (vval) E D(val To better keep track of the overall privacy cost, we use the current state-of-the-ee privacy accounting technique based on the notion of the Privacy Loss Random Variable (PRV) [7]. Here, we provide more details about the background of the composition of differential privacy and the privacy accounting techniques we use.
Background: Composition of Differential Privacy ("Privacy Accounting"). In practice, multiple differentially private mechanisms may be applied to the same dataset, denoted as M(D) = Mi M2(D) (D), (2(D))) Differential privacy offers strong composition guarantees, and the guarantees are derived by various composition theorems or privacy accounting techniques, including the basic composition theorem (4. advanced composition theorem [18), and Moments Accountant [1] For example, the basic composition theorem states that if Mi is ($1, ($1,81)-DO S1P and M₂ is (52, 02)- DP, then the composition of M₁ and M2 is (51 + E2; d1 + -DP In our scenario, each individual
mechanism is the release of T (D (vvl)) for each of (val) e D(val), and we would like to keep track of the privacy loss of releasing all of them.
Privacy Accounting Techniques based on Privacy Loss Random Variable (PRV). To better keep track of the privacy cost, we use the current state-of-the-arr privacy accounting based on the notion of the Privacy Loss Random Variable (PRV) [17]. The PRV accountant was introduced in For any DP algorithm, one can easily compute its (s, 6) privacy
37 and later refined in 336 25 guarantee based on the distribution of its PRV. The key property of PRVs that, under (adaptive) composition, they simply add up: the PRV Y of the composition M .M M2 .... M₁ is given by Y = convolving the distributions of Y,, Y2.... Yr. Prior works (36] 25 approximate the distribution of PRVs by truncating and discretizing them, then using the Fast Fourier Transform (FFT) efficiently convolve the distributions. In our experiment, we use the based accountant from 25 the current slate-of-the-a privacy accounting technique.
Ei= Yú, where Y, the PRV of M, Therefore, one can then find the distribution of Y by
DDirectly privatizing 2 (u (i-an) is very difficult. Releasing more privatized statistics for the of privacy analysis common DP. e.g.. DP-SGD (1 releases all privatized gradients.
'Multiple DP mechanisms can be adaptively composed in the sense that the output of one mechanism can be used an input to another mechanism, MDD) = Mi M2(D) = M.D.
34

---

E Additional Experiment Settings & Results
E.1
Datasets
comprehensive list of datasets and sources is summarized in Table 7 Similar to the existing data valuation literature [3 39 30 60), preprocess datasets for ease of training. For Fraud, Creditcard, and all datasets from OpenML, we subsample the dataset to balance positive and negative labels. binarize the label by considering [ 1]. For the
For these datasets, if they have multi-class, image dataset MNIST, CIFARIO I0, we apply a ResNer50 [27 that is pre-trained on the ImageNet dataset the feature extractor. This feature extractor produces 1024-dimensional vector for each image. We employ sentence embedding models [54] to extract features for the text classification dataset AGNews and DBPedia, and the extracted features are 1024-dimensional vectors for each text instance. We perform L2 normalization on the extracted features as part of the pre-processing step.
The size of each dataset we use is shown in Table 7 For some of the datasets, we use a subset of the full set. We stress that we are using a much larger size the dataset compared with prior data valuation literature [30 39] 60) (these works usually only pick very small subset of the full dataset, e.g., 2000 data points for binarized CIFARI0). The validation data size we use is 10% of the training data size.
Dataset
Number of classes
Size of dataset
Source
MNIST
10
50000
CIFARIO
10
50000
38
AGnews
4
10000
665
DBPedia
14
10000
2
Click
2
2000
https://www.opntt apenmmlorggd/1218
Fraud
2
2000
Creditcard
2
2000
Apsfail
2
2000
https://www.pentt
Phoneme
2
2000
https://ww..penn. org/d/1489
Wind
2
2000
https://www.opent org/d/847
0ttp://ww..eemml..cg///8//8
Pol
2
2000
https: fttp:::/wwww.pemma/ org/d/722
CPU
2
2000
htttps://www.opeee org/d/761
2DPlanes
2
2000
https:
bttpp:://ww.oog http:///wwwoppm..... wwtpp//wwww.oo//////.......
Table 7: A summary of datasets used in Section 6
experiments.
E.2 Settings & Additional Experiments for Runtime Experiments
For the runtime comparison experiment in Section 6. we follow similar experiment settings from prior study 440) and we sample data points from a d-dimensional standard Gaussian distribution. The labels are assigned based on the sign of the sum of the features.
synthetic binary classification dataset. To generate the synthetic dataset,
We choose range of training data sizes N, and compare the runtime of both TKNN/KNN-Shaple at each N. We use 100 validation data points. For Figure 2 in the maintext, the data dimension d = 10. Here, we show additional experiment results when d' 100. As we can see from Figure 5 again TKNN-Shapley achieves better computational efficiency than KNN-Shapley across all training data sizes, and is around 30% faster than KNN-Shapley for large N.
E.3
Settings Additional Experiments for Distinguishing Data Quality Experiments
E.3.1
Details for Mislabel/Noisy Data Detection Experiment
In the experiment of mislabeled (or noisy) data detection, we randomly choose 10% of the data points and flip their labels (or add strong noise to their features). For mislabel data detection, we flip 10% of the labels by picking an alternative label from the rest the classes uniformly at random. For noisy data detection, add zero-mean Gaussian noise data features, where the standard deviation of the
35

---

Runtime Comparison (d 100)
KNN- Shapley
Runtime seconds)
200
TKNN TKNN-Shapley
150
100
50
0
0
50000 100000 150000 200000
# Training Data Points
Figure 5: Runtime comparison of TIKNN-Shapler and KNN-Shapley across various training data sizes N when data dimension d = 100. The plot shows the average runtime based on 5 independent runs. Experiments were conducted with an AMD 64-Core CPU Processor.
Gaussian noise added to each feature dimension is equal to the average absolute value of the feature dimension across the full dataset.
E.3.2 Additional Experiment Results for Private Setting
Table 8 provides comprehensive comparison of DP-TKNN-Shaple and DP-KNN-Shaplee We conducted the experiments on DP- DP-KNN--SO -P--Nll- with subsampling on only half of the datasets due to the considerable computational cost (at least 30x longer execute compared to its non-subsampled counterpart). Additionally, because DP-KNN-Shappl value score of each data holder, it does not have the property of being robust against collusion.
injects Gaussian noise independently into the
As evidenced by the results, DP- BOP-TKNN-Shaple privacy-utility tradeoff compared to OP-KNN-Shien Shapley without subsampling across all datasets. Even when comparing with OP-KNN- -hapley with subsampling, MrKKNNShaaplee still shows superior performance, and often significantly outshining this time-intensive and collusion-susceptible baseline. Notably, DP-TKNN- -hapleyy manages to maintain high AUROC values even when E = 0.1. The low performance of DP- OP-KNN--S OP-KNN-Shapley can be attributed to its relatively high global sensitivity, discussed in Appendix B.3.
consistently demonstrates markedly superior
E.3.3
Additional Experiment Results for Non-private Setting
Here, we show full experimental results for various data valuation techniques in mislabel/noisy data detection scenarios. summarized in Tables 9 and 10 In line with the main text findings, TKNN- Shapley exhibits performance largely on par with KNN-Shapley across the majority of datasets, demonstrating that TKNN- Shapley effectively mirrors KNN- ENN-Shapley's ability discern data quality. In addition, both KNN- Shapley and TKNN- Shapley significantly outperform traditional retrain-based data valuation techniques (LOO, Data Shapley, and Data Banzhaf), corroborating observations made in existing studies [31 52). The inferior performance of Data Shapley can be attributed to sample inefficiency and the inherent randomness during the retraining process (60
Settings for L.OO, Data Shapley and Data Banzhaf. Following the experiment settings in 23 39
we use logistic regression as the ML model for these techniques. For Data Shapley, we use permutation sampling [48) for estimation. For Data Banzhaf, we use the maximum maxiiuu--sappl--ree -amplc-reusee (MSR) algorithm x000 longer time compared with both TKNN/KNN-Shapler
[60] for estimation. For each dataset, we train models on 10,000 subsets (which takes more than
E.3.4 Ablation Study on the Choice of Threshold for TKNN-Shapley
KNN-Shapley is known for being effective on wide range of choices of K [29]. In this experiment, we study the impact of different choices of T on the performance of TKNN-Shapley on the tasks
of mislabeled/noisy data detection. The results are shown in Table and 12
As we can see, the
36

---

Mislabeled Data Detection
Noley Data Detection
DP-KNN-Shapley [no subsampling)
OP-KNN-Shaple (with subssmppling)
-S--aly- (no salesampling)
DP-KNN-Shuphe (with subsampling
Dataset
Dr-TkWN-
DP-TKNN-Shappey
0.1
0.883 (0.017)
0.49 (0.024)
0.733 (0.611)
0,692 (0.014)
0.494 (0.023)
0.615 (0.01)
2dplames
0,912 (0,009)
0.48% (22)
0.815 (0.006)
0.706 (0.0444)
0,494 (0.012)
(0.0014)
0.913 (0,009)
0.504 (0.019)
0.821 (0.005)
0.705 (0.007)
0,495 (0.011)
0.665 (0.004)
0.1
0.816 (0,011)
0.5 (0.014)
0.692 (0.011) 1)
(1648 (0.028)
0.475 (0.942)
0.566 (0.01)
phoneme
0,5
0.826 (0.007)
0.497 (0.011)
0.738 (0.003)
0.633 (0.014)
0.536 (0.033)
0,588 (0,004)
0.826 (0,005)
0,486 (0.D1)
0,741 (0.002)
0.655 (0.016)
0,494 (0.071)
(0.0015
0.1
0.932 (0,007)
0.49 (0. (0.028)
0,881 (8.005)
0,805 (0.057)
0.42 (0.074)
0.709 (0.011)
CPU
0.5
0.946 (0.004)
0.507 (0.029)
0.928 (0.002)
(0.8((000077)
0.472 (0.992)
0.746 (0.00F)
0.948 (0.002)
0,512 (0.008)
0.931 (0.002)
0.839 (0.003)
0.455 (0.979)
0.748 (0.002)
0.1
0.661 (0.008)
0.511 (0.026)
0.584 (0.011)
0.558 (0.017)
0.479 (0.115)
0.519 (0,014)
Creditcard
0.5
0.663 (0.008)
(0.021)
(0.011)
0.571 (0.058)
0.513 (0.089)
(0.008)
0.668 (0.005)
0.491 (0.0266
0.627 (0.009)
0,585 (0.048)
0.525 (0.107)
0.545 (0.006)
0.1
0.566 (1.017)
0.512 (0.01.3)
0.511 (0.024)
0.55 (0.012)
0.439 (0.094)
0.497 (0.017)
Click
0.5
0.567 (0.013)
0.502 (0.018)
0.529 (0.012)
0.555 (0.01)
0.506 (0.971)
0,503 (0.018)
0.567 (0.007)
0.502 (0.021)
0.532 (0.01)
0.559 (0.009)
0.488 (0.076)
(0.017)
0.1
0.861 (0.021)
0.489 (0. (0.022)
0.836
0.622 (0.167)
0.464 (0.282)
0.557 (0.017)
Wind
0.5
0.583 (0.002)
0,511 (0.021)
0.873 (0.004)
0.668 (0.055)
0.554 (0.282)
0.501 (0.007)
0.882 (0.002)
0,186 (0.022)
0.875 (0.001)
0,681 (0.032)
0.595 (0.257)
0.605 (0,008)
0.1
0.947 (0.0044
0.497 (0.02)
(0.083)
0.468 (0.127)
Fraud
0.5
0.952 (0.002)
0.502 (0.022
0.85 (0.017)
0.548 (0.192)
0.953 (0.003)
0.502 (0.008)
0.859 (0.007)
0.497 (0.162)
0.1
0,903 (0.078)
0.501 (0.018)
0,693 (0.2)
0.456 (0.357)
Apsfail
0.5
0.952 (0.001)
0.521 (0.023)
(0.014)
0:189 (0.139)
0,952 (0.0)
0.49 (0.031)
0,882 (0.003)
0:494 (0.179)
0.1
0.844 (0.006)
0.508 (0.0122
0.605 (0.082)
0.53 (0.212)
Pol
0,5
0.858 (0.006)
(0.029)
0.673 (0.039)
0.626 (0.153)
0.857 (0.001)
0.516 (0.02)
0.695 (0.02)
0.622 (0.195)
0.1
0.801 (0.002)
0.492 (0.007)
0,841 (0.002)
0.384 (.381 (0.129)
MNIST
0.5
0.948 (0.002)
0:155 (0.005)
0,573 (0.001)
0.389 (0.125)
0.958 (0.002)
0,495 (005)
0.811 (0.002)
0.4 (0.007)
0.1
0.924 (0.002)
0.496 (0.0144
(0.002)
0.558 (0.913)
CIFARIO
0.5
0.936 (0.002)
0.497 (0.01.2)
0,847 (0.004)
0.560 (0.009)
0.949 (0.003)
0.497 (0.0112
0,852 (0.001)
0.560 (0. (0.006)
0.1
0.725 (0,002)
0,191 (3.002)
0,611 (0.003)
0:121 (0.065)
AGNews
0.733 (0,005)
0,492 (0.0012)
0.621 (0.001)
0,426 (0.075)
0.738 (0.002)
0.494 (0.0002)
0.627 (0.001)
0,426 (0.075)
0.1
0.652 (0.005)
0.499 (1..0022
0.579 (0.002)
0.360 (0.07)
DBPedia
0.5
0.654 (0.002)
0,199 (0.002)
0.586 (0.002)
0,360 (0.09)
0.657 (0.001)
(0.002)
0.588 (0.001)
0,361 (0.07)
Table 8: Privacy-utility tradeoff of DP-TKNN-Shapley and DP-KNN- for mislabeled/noisy data detection task on 13 datasets. We show the AUROC at different privacy budgets (We set 5 = 10 for MNIST. CI, AGNews, and PBPedia, and we set 8 = 10 for the rest of dataset, following the common rule of 1/N). The higher the AUROC is, the better the method is. We show the standard deviation of AUROC across 5 independent runs in O. The results for DP-KNN-Shapleg with subsampling are omitted for half of the datasets as requires a significant amount of runtime.
performance of TKNN-Shapley is quite stable on a wide range of choices of T. For example, for 2dPlanes dataset, the performance of TKNN-Shapley only varies < 0.032 between 7 E -0.6,,1066) Moreover, T Rs -0.5 is a relatively robust choice of the threshold value. Hence, hyperparameter tuning is not difficult for TKNN-Shapley,
This is not too surprising; the formula of TKKN--Shalee (in Equation (7)) shows that regardless of the choice of т, if a training data point is within the threshold but has a different label from the validation data, then its value is necessarily negative. At the same time, the points that share same label as validation data are guaranteed to have a positive value. The choice of 7 only decides the magnitude but not the sign. As data valuation methods only rely on the rank of data values to perform data selection, the performance of TKNN- TKNN-Shapley is relatively robust to the choice of 7 in identifying mislabeled data points (who get negative values). A similar argument also applics to the task of noisy data detection: noisy data is typically far from the population; hence, as long as T is not too large, the noisy data will receive value score close to O. On the other hand, clean data will receive a positive value score, and the choice of 7 only affects the magnitude of the data value but not the sign.
Ideally, we would like to set a threshold such that for most of the queries, there are a certain amount of neighbors whose distance to the query is below the threshold. One possible way to do this is simply picking a 7 that optimizes the final validation accuracy of the TKNN classifier (note that TKNN is very efficient in hyperparameter tuning).
37

---

Dataset
TKNN-Shapley
KNN-Shapley
Data Shapley
LOO
Data Banzhaf
2DPlanes
0.919
0.913
0,552
0.458
0.548
Phoneme
0.826
0.873
0.525
0.484
0.604
CPU
0,946
0.932
0,489
0.496
0.513
Fraud
0.96
0.967
0,488
0.495
0.534
Creditcard
0.662
0.646
0.517
0.487
0,536
Apsfail
0,958
0.948
0,496
0.485
0.506
Click
0.572
0,568
0.474
0.504
0,528
Wind
0.889
0.896
0.469
0.456
0,512
Pol
0.871
0.928
0.512
0.538
0,473
MNIST
0.962
0.974
CIFAR10 0,957
0,991
AG News 0.956
0.971
DBPedia
0.981
0.991
Table 9: Full Table for the AUROC of Mislabel Data Detection (non-private setting). The results for LOO, Data Shapley, Data Banzhaf are omitted for MNIST, CIFARIO, AGNews and DBPedia as they
require a significant amount of runtime (prior works typically subset for MNIST and CIFAR10
23 39 60))
Dataset
TKNN-Shapley
KNN-Shapley
Data Shapley
LOO
Data Banzhaf
2DPlanes
0.705
0.718
0.545
0,504
0,656
Phoneme
0.71
0.706
0.49
0.531
0.631
CPU
0.751
0.726
0.527
0,459
0,531
Fraud
0.818
0.794
0,502
0.526
0.582
Creditcard
0.611
0.64
0,535
0.513
0.506
Apsfail
0.841
0.666
0.533
0.465
0.566
Click
0.558
0.547
0.461
0.503
0.572
Wind
0.691
0.794
0.495
0.488
0.54
Pol
0.68
0.79
0.526
0.503
0.588
MNIST
0.613
0.815
CIFARIO
0.85
0.935
AG News 0.804
0.746
DBPedia
0.719
0.88
Table 10: Full Table for the AUROC of Noisy Data Detection (non-private setting). The results for LOO, Data Shapley, Data Banzhaf are omitted for MNIST, CIFARIO, AGNews and DBPedia as they require a significant amount of runtime (prior works typically use subset for MNIST and CIFARI0
23 39 60
For completeness, we also show the impact of different choices of K on the performance of KNN- Shapley in Table and [4] As we can see, KNN-Shapley's performance is quite stable against the different choices of K.
38

---

Dataset
0.1
0.2
0.5
2dPlanes
0.911
0.188
0.862
0.725
0.553
CPU
0.952
0.956
0.954
0,952
0.95
0,943
0.917
0.895
0.834
Phoneme
0.79
0.799
0.805
0.811
0.825
0.834
0.844
0.859
0.861
Fraud
0.961
0.956
0.951
0.954
0.959
0.931
0.884
0.75
Creditcard
0.653
0.671
0.668
0.669
0.662
0.652
0.648
0.606
0.539
Apsfail
0,959
0.952
0.962
0.967
0.962
0.952
0.924
0.899
0,851
Click
0,576
0.552
0.557
0.56
0.568
0.556
0.547
0.538
0.522
Wind
0.875
0.882
0.885
0.879
0.888
0.775
Pol
0.847
0.854
0.864
0.871
0.875
0.878
01.99
0.878
0.86
Table 11: Impact of different choices of for TKNN-Shapley on the performance of mislabel data detection.
Dataset
0.1
0.2
0.3
0.4
0.5
0.66
0.7
-0.8
0.9
2dPlanes
0.671
0.691
0,704
0.696
0.705
0.694
0.678
0,626
0.528
CPU
0.691
0.687
0,696
0.709
0.751
0.777
0.789
0,786
0.75
Phoneme
0.688
Fraud
0.758
0.781
0.804
0.809
0.818
0.837
0.847
0.814
0.664
Creditcard
0.579
0.576
0.585
0.597
0.611
0.624
0.642
0.626
0.574
Apsfail
Click
0.53
0.544
0.537
0.539
0.558
0.563
0.521
0.521
0.539
Wind
0,592
0.612
0.637
0.663
0.691
0.727
0.747
0.754
0.719
Pol
0.594
0.638
0.643
0.661
0.68
0.682
0.712
0.721
0.699
Table 12: Impact of different choices TKNN-Shapley on the performance noisy data
detection.
Dastaset
R ==1
==
K 3
4
K =
6
K =
K =
K =
K 10
K 1I
K 12
K 13
K 14
AdPlones
0.944
0.914
0.15
0915
0.16
0.955
0.955
0.944
0.915
0.915
0.914
0.1
0.955
0.898
0.896
CPU
0.56
0.936
0337
0937
01377
09337
0.988
0.937
0336
0354
0.932
03529
0128
Q927
0.921
Phoneme
0.899
0.81
0.822
0.82
0.864
0865
0.888
0.86
0.869
0.711
0.871
0.511
0371
0.74
0.86
Fraud
0972
0.922
0971
0.71
0972
0.972
0972
0.971
0.71
0.971
0.97
0.677
0.966
Credittcrd
0.638
Click
0.967
0919
Table 13: Impact of different choices of K for KNN- on the performance of mislabel data detection.
0.706
0706
0.111
0.766
0.76
Fraud
0.786
0.788
0.92
0.994
0794
0795
0797
0.97
0.79
0.801
0811
0.822
Creditcard
0.637
0.638
0.66
0.688
0.6
0.62
0.63
0.64
0.665
0.665
0.615
0.612
0.63
0.635
0.54
Apsfail
0.667
0.677
0.677
0.66
0.66
0666
0.66
0668
0.71
0.674
0.078
0/63
0.60
0.11
0.763
Click
0.544
0.547
0.552
0.549
0.547
0.549
0.549
0.567
0.548
0.544
0.544
0.543
0.543
0.544
0.545
Wind
0.786
0.796
0.795
0.796
0.794
0.795
0.792
0.791
0.791
0.79
0.788
0.788
0.788
0.789
0.791
Poi
0.789
0.788
0.788
0.788
0.79
0.79
0.788
0.787
0.786
0.786
0.787
0.79
0.786
0.786
0.785
Table 14: Impact of different choices of K for KNN-Shapley on the performance noisy data
detection.
39


Reviews:
[{"review_id": "pDRYbIOjdt", "reviewer": "Reviewer_qAKo", "summary": "The paper proposes a new variant of KNN-Shapley named TKNN-Shapley from which they derive a privacy-preserving data value approach DP-TKNN-Shapley. They conduct experiments to showcase that their approaches obtain better privacy-utility tradeoff and comparable performance to baselines. ", "questions": "These are provided in the Weaknesses section above.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Data valuation has limited work on privacy-preserving variants and incorporating privacy in these methods (especially KNN-Shapley) is a timely problem.\n- The empirical results demonstrate the usefulness of the TKNN-Shapley and DP-TKNN-Shapley approaches.\n- As a standalone variant, TKNN-Shapley has linear time complexity which is a logarithmic factor improvement over KNN-Shapley while incurring minimal drop in performance. The non-recursive nature of the proposed solution is beneficial for privacy amplification via subsampling as well.", "weaknesses": "- My main issue with the work is regarding motivation and presentation. Currently, the need for a DP variant to standard data valuation approaches is motivated in Section 3. However, a number of key experiments (such as with regards to the membership inference attack) are deferred to the appendix and are even then, fairly limited. In my opinion, the need for a DP variant only exists if there is a risk for membership inference, that then leads to the research question-- _is it possible that data valuation approaches leak membership information?_ If the answer is yes, then the paper is very well-motivated and DP-TKNN-Shapley is a significant contribution _if it is resilient to such adversarial scenarios_. \n- However, even though the membership inference attack proposed provides an affirmative answer to the first research question (as the results in the appendix indicate) it is not covered in the main paper in sufficient detail. I believe the authors need to make the following changes: 1) provide a simple version of the membership inference attack (MIA) algorithm in the main paper (Section 3) and present basic attack results (Table 3 in appendix) to motivate the need for a privacy-preserving data valuation algorithm; 2) evaluate DP-TKNN-Shapley for the MIA paradigm to demonstrate its effectiveness under such adversarial influence. Here the latter is highly significant. Otherwise I feel that the problem is not well-motivated and some necessary results are missing from the work. To reiterate, without an extant threat to inferring membership, there should be no need for a private version of KNN-Shapley. \n- While the approach itself is quite simplistic, I am inclined to agree with the authors' statement that simplicity is better when private solutions need to be implemented.\n- Is there a reason why the authors have not considered the \"learning with weighted samples\" or \"point addition/removal\" application experiments for TKNN-Shapley evaluation as in previous work (refer to [1-2]) on data valuation?\n- The authors should also go through the manuscript and fix any minor formatting errors and typos-- for example, Table 10 and 11 captions in the appendix should read $K$ instead of $\\tau$.\n\nReferences:\n- [1] Kwon, Yongchan, and James Zou. \"Beta shapley: a unified and noise-reduced data valuation framework for machine learning.\" arXiv preprint arXiv:2110.14049 (2021).\n- [2] Wang, Tianhao, and Ruoxi Jia. \"Data banzhaf: A data valuation framework with maximal robustness to learning stochasticity.\" arXiv preprint arXiv:2205.15466 (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments!\n\n**Q1. [Improving the motivation section]** *“I believe the authors need to make the following changes: 1) provide a simple version of the membership inference attack (MIA) algorithm in the main paper (Section 3) and present basic attack results (Table 3 in appendix) to motivate the need for a privacy-preserving data valuation algorithm; 2) evaluate DP-TKNN-Shapley for the MIA paradigm to demonstrate its effectiveness under such adversarial influence.”*\n\n**A:** We thank the reviewer for the very concrete suggestions! Here are our changes to the paper according to your two suggestions:\n- In Section 3, we have enriched the text with a high-level summary of the MI attack proposed in Appendix C.2.2, and we have moved part of the MI attack results to the main text. For completeness, we additionally conducted the experiment of the proposed MIA against (non-private) TKNN-Shapley (**see Q1 in global response and Table 4 in the Rebuttal’s pdf**). The result shows that both KNN-Shapley and TKNN-Shapley serve as an additional channel for leaking membership information of private data. \n- We additionally conducted the experiment of the proposed MIA against DP-TKNN-Shapley (**see Q1 in global response and Table 5 and 6 in the Rebuttal’s pdf**). Compared with the result on non-private TKNN-Shapley, the overall attack performance drops to around 0.5 (the performance of random guess). The result shows that DP-TKNN-Shapley is indeed very effective against membership inference attacks. Moreover, we stress that differential privacy is a robust solution against any attacks in an information-theoretic sense. Hence, the privacy protection is not only for the MI attack we design here, but also for any future attacks. \n\nWe have added these additional results to Appendix C.2.2. \n\n**Q2. [Why not consider \"learning with weighted samples\" or \"point addition/removal\" application experiments?]** \n\n**A:** Thanks for the great question! We would first like to point out some limitations of using these two tasks to evaluate a data value notion. \n\nFor \"learning with weighted samples\" experiment, the performance is highly dependent on the *distribution* of data value scores. Imagine that there are a very small group of data points that receive extremely high value, weighted training based on the value scores will result in poor performance as the learning algorithm will be “lazy” to fit the rest of data points that receive lower value scores. \n\nFor “point addition/removal” experiment, the performance is highly dependent on the diversity of selected data points. However, a reasonable data value notion typically needs to satisfy “symmetry axiom”, which is being interpreted as fairness. Hence, if one selects data points with high values, it is likely that the selected data points lack diversity, as similar data points are required to receive similar value scores. In fact, preliminary theoretical and empirical results [3] show that the Shapley value as well as other cooperative-game-theory-based data valuation can result in arbitrarily low model performance in the worst case. \n\nHaving said that, we additionally conducted the “point removal” experiment (**see Q2 in global response**) where we remove the data points that receive the lowest data value scores, then train the model on the remaining of the dataset and check whether the test accuracy is actually improved. Here, we remove at most 10% of the full dataset. In this case, the dataset diversity is not being affected a lot by removing bad training data points. The specific settings for the model architecture used in the experiment follow from [2]'s Appendix D.3.2, and the specific settings for the datasets follow from the mislabeled data detection experiment (Appendix F.3.1). **Figure 7 in the Rebuttal’s pdf** shows results on the private setting (where we use $\\varepsilon=1$), and **Figure 8 in the Rebuttal’s pdf** shows results on the non-private setting. Similar to the results for mislabel/noisy data detection experiment, we observe that **(1)** DP-TKNN-Shapley significantly outperforms the naively privatized KNN-Shapley in terms of privacy-utility tradeoff; **(2)** non-private TKNN-Shapley achieves comparable performance as the original KNN-Shapley in discerning data quality. \n\n[1] Kwon, Yongchan, and James Zou. \"Beta shapley: a unified and noise-reduced data valuation framework for machine learning.\" AISTATS 2022.\n\n[2] Wang, Jiachen T., and Ruoxi Jia. \"Data banzhaf: A robust data valuation framework for machine learning.\" AISTATS 2023.\n\n[3] https://openreview.net/pdf?id=kz6rsFehYjd (Section 4).\n\n\n**Q3. [Typos]** \n\n**A:** Thanks for the catch! We have taken another pass of the paper to address the typos. \n"}, {"review_id": "Sk2pqyJJAe", "reviewer": "Reviewer_QHAC", "summary": "The paper addresses the problem of evaluating and assigning a value to the quality of training data for KNN in a privacy preserving way. Therefore, it first introduces an adaptation of the KNN-Shapley algorithm, namely TKNN-Shapley which due to its non-recursive way of implementation facilitates integrating differential privacy. The paper then finally proposes how to do that and provides empirical evaluation.", "questions": "Q1: Can you specify the selection of the threshold in TKNN?\n\nQ2: Could you provide an explanation on the runtime of TKNN (O(N)) instead of the O(N log N)?\n\nQ3: Could you extend the privacy analysis of the release of all valuation scores of the full dataset - and show how it grows with the number of data points?\n\nQ4: Could you specify what the \"naively privatized KNN-Shapley\" baseline from line 324 refers to exactly? Without that understanding, it seems hard to follow on what are the improved privacy-utility trade-offs mentioned in the abstract.\n\n\n", "limitations": "There seems to be no proper limitation section, if I haven't overlooked any. Adding a discussion on the strength of privacy protection, the ethical aspects of valuating private data, and the danger of wrong incentives for individuals should be discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I did really enjoy reading the paper due to its highly accessible flow, good motivation (in terms of demonstration of the privacy risks), the gentle introduction into the KNN-Shapley, the intuitive explanation why an integration of privacy is difficult, and then the solution in terms of an adapted algorithm and the integration of differential privacy.\n\nThe experimental evaluation seems sound and thorough, so does the supplementary material.\n\nThe figures (especially Figure 1) serve well the purpose of illustrating the approach described in the work.", "weaknesses": "My main concern is the selection of the threshold in the TKNN. It seems crucial for the success of the algorithm, yet I could not find a good intuition and evaluation of the choice of this parameter. It would be helpful if the rebuttal could provide information about it.\nEspecially, I am curious about cases where there remain only few neighbors in the area below the threshold. \n\nAdditionally, I would enjoy reading more in the main paper around lines 310-312 about how subsampling can be efficiently integrated into the algorithm. Maybe, some intuition from Appendix E.2 could be migrated there?\n\nEven after consulting Appendix E.3, it remains unclear to me what the final privacy costs of releasing all Shapley-scores for the dataset would be and how they depend on the size of the test dataset.\n\nThe choice of the privacy parameter delta (10e-4) for, e.g. the 2DPlanes dataset seems relatively high. The rule of thumb would be to choose it 1/N with N being the number of private data points. From https://www.openml.org/search?type=data&sort=runs&id=215&status=active, I understand that the dataset has north of 40k data points, so choosing delta=10e-5 might be more appropriate.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments!\n\n**Q1 [Selection of the threshold in TKNN]**\n\n**A:** In our experiment, we found that the performance of TKNN-Shapley is quite robust to the selection of the threshold $\\tau$. In Section 6, we set the threshold $\\tau = -0.5$ (note that cosine distance ranges from $[-1, +1]$) across all experiments. **In Appendix F.3.4, we conduct the ablation study** and we find that the performance is relatively stable across a wide range of $\\tau$. This is not too surprising; the formula of TKNN-Shapley (in Equation (7) in Appendix D.2.1) shows that regardless of the choice of $\\tau$, if a training data point is within the threshold but has a different label from the validation data, then its value is necessarily negative. At the same time, the points that share same label as validation data are guaranteed to have a positive value. The choice of $\\tau$ only decides the magnitude but not the sign. As data valuation methods only rely on the rank of data values to perform data selection, the performance of TKNN-Shapley is relatively robust to the choice of $\\tau$ in identifying mislabeled data points (who get negative values). A similar argument also applies to the task of noisy data detection: noisy data is typically far from the population; hence, as long as $\\tau$ is not too large, the noisy data will receive a value score close to 0. On the other hand, clean data will receive a positive value score, and the choice of $\\tau$ only affects the magnitude of the data value but not the sign. \n\nIdeally, we would like to set a threshold such that for most of the queries, there are a certain amount of neighbors whose distance to the query is below the threshold. One possible way to do this is simply picking a $\\tau$ that optimizes the final validation accuracy of the TKNN classifier (note that TKNN is very efficient in hyperparameter tuning). \n\nAdditionally, we stress that the case where there are only a few neighbors whose distance to the query is below the threshold may not necessarily be bad. This may happen when the query is an outlier that is very far from the center of population. Hence, a reasonable classifier is supposed to assign low confidence for such a query for all classes. TKNN, in this case, is guaranteed to have such reasonable behavior. However, for KNN, the behavior is less predictable as it depends on the query example’s K nearest neighbors (which may still be far from the query in absolute distance).\n\nWe have enriched our Appendix F.3.4 with the above discussion. \n\n**Q2 [Intuition for DP-TKNN-Shapley with subsampling?]** *“Additionally, I would enjoy ... there?”*\n\n**A:** Thanks for the suggestion! We have enriched the intuition for the corresponding texts! At a high level, because of the non-recursive nature of TKNN-Shapley’s computation, incorporating it with subsampling becomes straightforward.\n\n**Q3 [How to compute the final privacy cost?]** \n\n**A:** **Privacy loss & training (private) set size:** As stated in Sec 5.2, if we view the release of all Shapley scores as a whole mechanism, then it satisfies Joint DP with the same privacy parameter as in Theorem 6. At a high level, this is because we only spend privacy budget to privatize the entire private set’s statistics *once*, and reuse the privatized statistics to calculate individual DP-TKNN-Shapley value, which does not increase the privacy cost (see Theorem 16).\n\n**Privacy loss & validation set size:** Modern PRV-based privacy accountant computes the privacy loss numerically (and hence the final privacy loss has no closed-form expressions). PRV accountant [1] is a standard practice in DP literature nowadays due to the tight privacy bound calculation.\n\n[1] \"Numerical composition of differential privacy.\" NeurIPS 2021\n\n**Q4 [Choice of $\\delta$]** *“The choice of ... be more appropriate..”*\n\n**A:** For 2DPlanes dataset, we follow the prior works [1-2] and use a size-2000 subset of the training set for experiment (see Table 5 in Appendix F.1 for the summary of datasets). Hence $\\delta=1e-4$ is reasonable. We note that size-2000 is already much larger compared with [1-2] (which only use a size-200 subset). We fix size-2000 to adapt the implementation from [1] easily. For completeness, we also conducted experiments on the full 2DPlanes and other datasets and use $\\delta = 10^{-5}$. **See Q1 in global response**. \n\n[1] \"Beta shapley: a unified and noise-reduced data valuation framework for machine learning.\" AISTATS 2022.\n\n[2] \"Data banzhaf: A robust data valuation framework for machine learning.\" AISTATS 2023.\n\n**We will provide enriched discussion for Q5-7 in \"official comment\".**\n\n**Q5 [Runtime of TKNN-Shapley]** \n\n**A:** The algorithm for computing TKNN-Shapley in $O(N)$ runtime is detailed in Appendix D.2.2. We have highlighted in Theorem 5’s statement to make sure the reader can find it easily. At a high-level, the efficient TKNN-Shapley computation leverages the property that the required quantities for its determination are fundamentally counting queries performed on the dataset $D_{-z_i}$, which can be easily computed from the same counting queries performed on the full dataset $D$. \n\n**Q6 [What is \"naively privatized KNN-Shapley\" baseline?]**\n\n**A:** For \"naively privatized KNN-Shapley\", we are referring to the two baselines we use in the experiments of Section 6.2.1. We have highlighted this point in the paper to avoid any confusion. These two baselines are detailed in the last paragraph of Appendix C.3.1 and Appendix C.3.2, respectively. \n\n**Q7 [Limitation Section]** *“There seems ... be discussed.”*\n\n**A:** The limitation of this work is discussed in the Conclusion section. We appreciate the reviewer’s suggestion for additional discussion on those interesting topics! Some discussion on the scope of privacy protection and the ethical aspects can be found in our Conclusion. See our enriched response in \"official comment\" for additional discussion on the danger of wrong incentives. "}, {"review_id": "KN2jvVfjDA", "reviewer": "Reviewer_SBGb", "summary": "The paper studies the privacy concerns surrounding KNN-Shapley, a prevalent method for data valuation. Authors introduce TKNN-Shapley, which employs the concept of differential privacy to protect privacy. Empirical tests demonstrate that TKNN-Shapley performs on par with KNN-Shapley in assessing data quality, while also providing a favorable balance between privacy.", "questions": "Please see limitations", "limitations": "1. The privacy risk of KNN-Shapley is not convincingly demonstrated. The evidence presented in Figure 2 and the corresponding figures in Appendix C only suggests that modifying certain data points can lead to changes in the Shapley score, but it's unclear if these changes are unique and can lead to a membership inference attack (MIA). Additionally, KNN is not easily susceptible to overfitting, which makes MIA less likely. Furthermore, in Figure 1, the assumption of a \"trusted\" center for data upload is not representative of real-world scenarios, where untrusted centers are more common and raise additional privacy concerns.\n\n2. Data valuation is not the sole and universally accepted method for evaluating the importance of training data. Alternative dataset scoring schemes, such as core-sets or general dataset distillation approaches may be more prevalent in the field. As a recommendation, further research on these alternative methods could be beneficial.\n[1] Feldman, Dan. \"Introduction to core-sets: an updated survey.\" arXiv preprint arXiv:2011.09384 (2020).\n[2] Wang, Tongzhou, et al. \"Dataset distillation.\" arXiv preprint arXiv:1811.10959 (2018).\n", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The presentation is generally good.\n2. The methodology is solid. The proposed TKNN-Shapley method provides a guarantee of differential privacy, which enhances the privacy protection of the data valuation process.\n", "weaknesses": "1. The research problem is quite narrow. The paper focuses on a specific metric (KNN-Shapley) for a narrow ask (data valuation), which may not arise wide interest in the ML community. \n2. The significance of the privacy leakage of KNN-Shapley is not convincing. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback about our presentation and methodology!\n\n**Q1. [Privacy risk of KNN-Shapley]** *“The privacy risk of KNN-Shapley ... can lead to a membership inference attack (MIA). Additionally, KNN is not easily ... less likely. Furthermore, in Figure 1, the assumption of a \"trusted\" center ... concerns.”*\n\n**A:** For ***“... it's unclear if these changes are unique and can lead to a membership inference attack (MIA)”***, we presented an instantiation of a membership inference attack on KNN-Shapley score (**summarized in the paragraph above Section 3.1 and detailed in Appendix C.2.2**). The attack is designed analogue to the *likelihood ratio test* attack on ML models [1]. The attack results in Appendix C.2.2 demonstrates that privacy leakage in data value scores can indeed lead to non-trivial membership inference attacks. We have highlighted the actual instantiation of MI attack as well as moving part of the attack results to Section 3 (in Figure 2) so that the reader will not miss this contribution. \n\nTo further improve the readability of Section 3, we also added a remark on the long history of the study of privacy risks underlying the aggregated statistics of a dataset (KNN-Shapey is one such example). The remark's content (*\"Brief background for the privacy risks in releasing aggregated statistics\"*) is outlined in **global response's Q4** for the reviewer’s reference :)\n\n[1] Carlini, Nicholas, et al. \"Membership inference attacks from first principles.\" S&P 2022.\n\nFor ***“KNN is not easily susceptible to overfitting, which makes MIA less likely”***, we’d like to clarify that we are performing MI attack against **KNN-Shapley instead of KNN classifier**. We have shown that MI attack on KNN-Shapley is possible and effective with a specific instantiation of MI attack. \n\nFor ***“the assumption of a \"trusted\" center for data upload is not representative of real-world scenarios, where untrusted centers are more common and raise additional privacy concerns”*** We appreciate the reviewer's valid point on the assumption of a \"trusted\" center for data upload. We would like to clarify the following three points: **(1) Existence of real-world examples:** Many AI data marketplaces (e.g., [1, 2]) we have seen are central servers that are implicitly trusted by the users, and the users can directly upload data to these servers for selling their data. The trustworthiness of these central servers is enforced through existing legal and regulatory frameworks (e.g., [3]). **(2) Common practice in many literatures for simplifying theoretical analysis:** Many studies in the domain of data marketplace [4, 5] assume the presence of a trusted central party to facilitate specific operations. This assumption isn't unique to our work, and this allows us to understand the privacy risks incurred by releasing data valuation results without the extra complexities of an untrusted central party. **(3) Our work establishes the foundation for future research on end-to-end privacy protection** Our work primarily focuses on the privacy risks associated with revealing data value scores, which need to be protected by incorporating differential privacy (DP). As we mentioned in Remark 2 as well as Conclusion section, the privacy risks of revealing individuals' raw data to a central server are indeed crucial but they represent a different category of privacy risks that need to be addressed via secure multi-party computation (MPC). In practice, MPC and DP should be used in conjunction to provide end-to-end privacy protection. An interesting follow-up of our work is to further incorporate DP-TKNN-Shapley with an MPC framework. We emphasize that this is a substantial endeavor on its own and worth a separate, dedicated research paper. Our work establishes the foundation for this interesting future research direction. \n\nIn other words, incorporating TKNN-Shapley with MPC is beyond the scope of our current work but stands as an important direction for future research.\n\n[1] Datarade https://datarade.ai/ \n\n[2] Innodata https://innodata.com/data-privacy-framework/ \n\n[3] https://innodata.com/data-privacy-framework/\n\n[4] Fernandez, Raul Castro, Pranav Subramaniam, and Michael J. Franklin. \"Data Market Platforms: Trading Data Assets to Solve Data Problems.\" VLDB\n\n[5] Agarwal, Anish, Munther Dahleh, and Tuhin Sarkar. \"A marketplace for data: An algorithmic solution.\" EC 2019.\n\n\n**Q2.** *“Data valuation is not the sole and universally accepted method for evaluating the importance of training data. Alternative dataset scoring schemes, such as coresets or general dataset distillation approaches may be more prevalent in the field.”*\n\n**A:** We acknowledge the relevance of coresets and dataset distillation approaches in the broader landscape of assessing training data importance. However, coresets and dataset distillation primarily focus on selecting/synthesizing a condensed but representative subset of a larger dataset. Although these techniques might assign some form of importance scores to individual data points, the interpretations and implications of these scores significantly differ from those of data valuation. Specifically, many data valuation techniques such as KNN-Shapley score possess a game-theoretic interpretation and carry essential fairness properties. These properties facilitate their application in data marketplace scenarios for equitable data pricing. In contrast, the importance scores derived from coresets and dataset distillation approaches may not provide an equitable valuation of data and thus might not be readily applicable for data pricing in a data marketplace. This divergence underscores the necessity and significance of the line of data valuation research.\n\nOn the other hand, we completely agree with the reviewer that coresets and dataset distillation are also important techniques, and studying them from the privacy perspective is definitely interesting future work."}, {"review_id": "62tGazopsx", "reviewer": "Reviewer_z2hx", "summary": "In this paper, the authors suggest a modified version of KNN-Shapley that aims to enhance the privacy of the data valuation procedure. They introduce TKNN-Shapley, which focuses only on neighbors within a $\\tau$ vicinity of the utilized data point instead of a fixed number of neighbors (k), and DP-TKNN-Shapley to ensure differential privacy by incorporating the Gaussian mechanism. The paper also includes numerical experiments comparing the efficiency of TKNN-Shapley to KNN-Shapley and demonstrates the competitive performance of TKNN-Shapley in both private and non-private settings for detecting mislabeled and noisy data. The proposed approach consistently performs well across all presented results.", "questions": "It would be helpful if the authors could clarify the following confusions: \n- line 265: where does the computational complexity $\\mathcal{O}(N)$ of the TKNN-Shapley comes from? \n- Concretely what privacy risks can the proposed methods address? I was not able to understand the concrete risks (apart from line 156 which is outside the scope of the paper).\n- How does the noisy/mislabeled data detection in the numerical experiments tie to addressing privacy risks? I am not knowledgeable in the privacy field so I would appreciate the clarification even if it is an obvious explanation.\n- line 251: I am a bit confused about the raw summation. I thought it is rather averaged over the validation set\n- I think KNN-Shapley uses K in the denominator of Equation (2). Otherwise, I don't think their equation (69)* holds. It doesn't seem to affect anything with the proposed method though. Happy to be corrected.\n\n\n*https://arxiv.org/pdf/1908.08619.pdf\n\n\n\n\n\n", "limitations": "The authors addressed several limitations in the submission. Additionally, I might add the sensitivity of DP-TKNN-Shapley's performance towards the choice of threshold $\\tau$ (though, probably not much further than what $k$ brings in the KNN-Shapley). \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is generally clear with good coverage of related work (although I humbly listed some improvement points later in my review). \n\nI think that the main strength of the paper is the performance of the proposed method in particular in terms of data-valuation efficiency and detecting mislabeled/noisy data in the private setting. It also seems to be competitive in the non-private setting, as such thresholding operator itself for finding neighbors appears to be a safe choice. The theoretical analysis and claims also seem sound as far as my knowledge extends.\n\n", "weaknesses": "I have concerns regarding  a. the originality of the proposed method and b. how it concretely addresses the privacy risks. \n\na. The method is a combination of well-known techniques such as KNN-Shapley, threshold-KNN, and differential privacy, and most of the analyses are adapted from previous derivations (eg KNN-Shapley) for this very specific algorithm. As such, the theoretical contributions in the paper are mainly to be attributed to the existing result. I will gladly stand corrected by the authors if my understanding is limited. All said, as I indicated in my previous comment, its performance seems significant in the demonstrated tasks and it is valuable work. \n\nb. Despite having read the privacy risk section, I do not immediately see how the privacy risks are addressed, which is the main claim of the work. I am fairly less confident in this argument though, as I am not familiar with the privacy field. I wish to understand this aspect better.\n\nOther than that, in terms of clarity, I believe there is room for improvement:\n- I think the background is too long and the actual contribution starts on page 6. This also seems to be because the proposed method combines existing strategies, but I think the background can still rather be cut short and more room can be created for experimental results or even the related work in the appendix section. \n\nFurther notes are presented in the form of questions below.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback about our experiment!\n\n**Q1. [Theoretical Contributions in this work]** *“The method ... is limited.”*\n\n**A:** We thank the reviewer for the comment. There are in fact at least two highly non-trivial theoretical contributions (in our opinion) in this work. \n\n**(1) The derivation of TKNN-Shapley is a unique contribution distinct from existing derivations for KNN-Shapley.** The proof of Theorem 5 is different from the one for KNN-Shapley, and the primary technical challenge is observing that $C_{\\tau}$ are sufficient for calculating $\\phi^{tknn}_{z_i}$. This is the key reason why TKNN-Shapley can be so effectively paired with differential privacy. Furthermore, only a few games have yet been discovered to have a polynomial-time algorithm for computing the exact Shapley value. The discovery of TKNN-Shapley is a contribution we believe will be of independent interest to the game theory community. \n \n**(2) Privatization of TKNN-Shapley with collusion resistance.** While Gaussian mechanism is a standard privatization method, this is already the reward of recognizing TKNN-Shapley’s special property mentioned above. **A more non-trivial theoretical contribution is that we show DP-TKNN-Shapley also satisfies *joint differential privacy* (elaborated in Appendix E.2.2 and Theorem 16).** This ensures the collusion resistance property of DP-TKNN-Shapley, which is important for the practical deployment.**\n\n**Q2.1. [*What* are the privacy risks are being addressed?]**\n\n**A:** **Membership inference (MI) attack:** In Section 3, we mainly discussed the privacy risks of revealing data value scores with respect to MI attack, i.e., confirming one's membership in a database. MI attack could pose significant privacy risks. For example, if a medical database is known to be a dataset for patients with specific conditions, confirming one’s membership in this database could disclose members' health status. We choose MI attack as our main example of the privacy risk as it has long been recognized as a fundamental privacy challenge across various domains, and such attacks have been extended well into the field of machine learning. \n\n**DP is not limited to mitigating MI attack:** It's crucial to highlight that differential privacy (DP) goes beyond just countering membership inference. At a high level, any changes to individual data that do not change the privatized output, and hence the privatized output cannot be used to infer much about any individual. \n\nThere's a rich history of studying privacy risks in aggregated dataset statistics, with KNN-Shapley being an example. For this topic, please refer to **Q4 in the global response** :)\n\n**Q2.2 [*How* the privacy risks are being addressed?]** \n\n**A:** Our primary tool for mitigating privacy risks is Differential Privacy (DP). DP has become the de-facto standard in the realm of privacy protection as differentially private algorithms offer robust, quantifiable, and provable privacy guarantees. Importantly, DP provides provable privacy guarantee against any potential privacy attacks, including those not yet developed. Thus, **if we have proved our DP-TKNN-Shapley algorithm is differentially private, we have the provable privacy guarantee** against both current and emergent privacy attacks. For a more direct illustration of how DP can protect against the privacy threat, we additionally conducted the experiment of evaluating the MI attack proposed in Appendix C.2.2 on DP-TKNN-Shapley (**see Q1 & Table 5 and 6 in Global Response**). Compared with the attack result on non-private TKNN-Shapley, the overall attack performance drops to around 0.5 (the performance of random guess). The result shows that DP-TKNN-Shapley is indeed very effective against membership inference attack. \n\n**Q3. [Background too long & the actual contribution starts on page 6?]** \n\n**A:** Thanks for the suggestion! We will cut some background and move more related works & experiment results to the main paper.\n\nWe would like to clarify that our contribution starts in Section 3 (page 4). To the best of our knowledge, the privacy risks of data valuation techniques have not been extensively studied before, and our work is the first to show that data valuation techniques indeed serve as another channel for privacy leakage, and we explicitly constructed a membership inference attack which achieves non-trivial attack performance. \n\n**Q4. [Runtime of TKNN-Shapley]** \n\n**A:** The algorithm for computing TKNN-Shapley in $O(N)$ runtime is detailed in Appendix D.2.2. We have highlighted it in Theorem 5’s statement to make sure the reader can find it easily. At a high-level, the efficient TKNN-Shapley computation leverages the property that the required quantities for its determination are fundamentally counting queries performed on the dataset $D_{-z_i}$, which can be easily computed from the same counting queries performed on the full dataset $D$. \n\n**Q5.** *“How does the noisy/mislabeled data detection in the numerical experiments tie to addressing privacy risks?”*\n\n**A:** The experiments related to noisy/mislabeled data detection were not designed with the intent to evaluate the privacy risk of DP-TKNN-Shapley. We have already established, through rigorous proof, that DP-TKNN-Shapley adheres to differential privacy guarantees (and we also have additional empirical experiments for the privacy guarantee as we mentioned in **Q2.2**). The primary objective behind these experiments is to investigate the *utility* of DP-TKNN-Shapley scores. It is important that the introduction of privacy-preserving technique does not come at a big cost of utility. After all, it is trivial to attain perfect privacy by simply assigning random value scores to each data point. Our experiments demonstrate that DP-TKNN-Shapley remain useful and informative even when privacy guarantees are enforced.\n\n**We will provide additional clarifications for Q4 and more questions in \"official comment\".**"}, {"review_id": "rwq9phrX1i", "reviewer": "Reviewer_i1sa", "summary": "The authors propose a relaxation of the KNN based Shapley valuation framework based on thresholding. By doing so, they are able to reduce the sensitivity associated with shapley valuation, and consequently apply DP to the mechanism.", "questions": "1. Could the authors kindly clarify how they validate the “goodness” of their TKNN method? Since the scores returned are “real numbers”, what does the AUROC measure actually capture? Similarly, what is the dependence of the threshold to determine the closeness of TKNN and KNN based shapley valuation?\n2. The primary contribution of this work is demonstrating a relaxation from the KNN to the TKNN setting. The application of gaussian noise to ensure DP is a standard technique. However, the authors motivate the need for DP with an experiment that motivates how privacy is leaked through membership inference. Could the authors clarify the setting once more? The authors claim that there are multiple colluding entities that aim to identify if a particular point is present or absent in the data valuation pipeline. To this end, they need to know the data point under consideration, which seems impractical given the setup described for data valuation (e.g., where data is contributed by individual entities for medical purposes).\n3. In algorithm 1, what is \t\\phi_z (Dattack \\cup z) formally defined as?", "limitations": "None discussed", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. First formalization of TKNN based shapley valuation.", "weaknesses": "1. Unclear what the primary contribution is. I conjecture it is the TKNN relaxation, and its reduced run time + closed form solution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback!\n\n**Q1. [Primary contribution]** \n\n**A:** Our contributions in this work are three-fold:\n\n1. **Uncovering the privacy risks of data valuation technique:** To the best of our knowledge, this work is the first formal study on the privacy risks associated with releasing data value scores. Another contribution is that we show KNN-Shapley cannot be easily modified to incorporate differential privacy, which calls for a more privacy-friendly approach for data valuation.\n\n2. **Introduction of TKNN-Shapley:** We found that Threshold KNN (TKNN), a simplified variant of KNN also possesses a closed-form Data Shapley formula and offers superior computational efficiency, reducing computation time to exact $O(N)$ from $O(N \\log N)$ compared to KNN-Shapley.\n\n3. **Incorporating TKNN-Shapley with differential privacy (DP-TKNN-Shapley):** Moreover, we demonstrate how TKNN-Shapley can be easily adapted to integrate differential privacy, offering a solution to the earlier limitations we identified with KNN-Shapley. Further to this, we show that DP-TKNN-Shapley brings several benefits such as collusion resistance.\n\n**Q2. [How did we evaluate the “goodness” of data valuation method?]** \n\n**A:** In our work, we follow the same evaluation method for data valuation techniques as the one used in the prior works in this field [1-2]: the effectiveness of data valuation techniques is quantified based on their performance in filtering out bad (mislabeled/noisy) data points. The underlying rationale is that a reasonable data valuation should assign lower scores to poor-quality data points, and higher scores to high-quality data points. Hence, we can measure the “goodness” of data value notions based on whether those poor-quality data points are actually receive lower value scores. In the task of filtering out bad (mislabeled/noisy) data points, we can use data valuation techniques to assign a value score for each data point, and exclude data points with the lowest scores. In other words, we are using data valuation scores as the evidence for classifying each data point as either “good” or “bad”. AUROC is a classic metric for evaluating the performance of such binary classification, and thus can be used as the measure for assessing the ability of a data value notion in *“distinguish between good and bad data”*. \n\nFor **“what is the dependence of the threshold to determine the closeness of TKNN and KNN based shapley valuation?”**, it is important to emphasize that **there isn't a single \"ground truth\" for data value scores**. The main criteria for evaluating the efficacy of a data valuation method are its ability to identify high-quality data points with high scores and low-quality data points with lower scores. The proximity of TKNN-Shapley and KNN-Shapley scores is not particularly meaningful in itself. Instead, these data valuation methods are compared based on their capacity to detect bad data.\n\n[1] Kwon, Yongchan, and James Zou. \"Beta shapley: a unified and noise-reduced data valuation framework for machine learning.\" AISTATS 2022.\n[2] Wang, Jiachen T., and Ruoxi Jia. \"Data banzhaf: A robust data valuation framework for machine learning.\" AISTATS 2023.\n\n\n**Q3. [Setting of Membership Inference Attack (Algorithm 1)?]** *“the authors motivate ... for medical purposes).”* \n\n**A:** **Setting of Algorithm 1**: In Appendix C.2.2, we consider the scenario where the server owns a dataset $D$ (collected from other users), and the attacker would like to know whether a target example $z$ is included in $D$. **Threat model:** in Appendix C.2.2, we consider that an attacker with the ability of (1) computing the value of any data point among any datasets (analogue to the setting of MIA against ML models where the attacker can train models on any datasets he/she constructs), and (2) crafting the data point it owns, send it to the server and obtain the data value score of its own data point. \n\nWe have further enriched the details in Appendix C.2.2 and we hope the attack setting is clear now :)\n\n**For “they need to know the data point under consideration, which seems impractical given the setup described for data valuation”**: we note that membership inference attack, i.e., confirming one's membership in a database, could pose significant privacy risks. For example, if a medical database is known to be a dataset for patients with specific conditions, confirming one’s membership in this database could disclose members' health status. Indeed, to conduct membership inference attack, the attacker needs to first know about the features of the target data point. This is also common in many scenarios, e.g., the height and weight of an individual sometimes may not be considered as sensitive, and what is considered as sensitive is the “membership” of an individual in a special database. In this work, we mainly use membership inference attacks to illustrate the privacy risks of data valuation techniques, as membership inference attacks have long been recognized as a fundamental privacy challenge across various domains, and such attacks have been extend well into the field of machine learning. \n\n[1] Carlini, Nicholas, et al. \"Membership inference attacks from first principles.\" S&P 2022.\n\n**Q4.** *“In algorithm 1, what is \\phi_z (Dattack \\cup z) formally defined as?”* \n\n**A:** $\\phi_z(D_{attack} \\cup {z})$ means the data value score of $z$ when the rest of the dataset is $D_{attack} \\cup {z}$, i.e., the full dataset has two identical copies of $z$. In other words, we are collecting and comparing the KNN-Shapley of $z$ between the cases of **(1)** the rest of the dataset contains its identical copy and **(2)** the rest of the dataset does **not** contain its identical copy. The intuition of the attack is as follows: if the target point $z \\in D$, then $\\phi_z(D)$ will be closer to the values in case 1, and if the target point $z \\notin D$, then $\\phi_z(D)$ will be closer to the values in case 2. \n\n"}, {"review_id": "FFpQaAuzYS", "reviewer": "Reviewer_yczn", "summary": "This paper proposes an approach for data valuation that tries to be privacy-preserving by design. More precisely, the proposed method aims at computing the data valuation of a point through its Shapley value for the k-nearest neighbours classifier (knn) in a differentially-private manner. ", "questions": "See weakness section for the main points raised. ", "limitations": "OK.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and the authors have clearly summarized the main contributions of the paper. The background notions on Shapley values as well as knn Shapley values are also clearly explained. \n\nAn analysis of the privacy risks associated to the release of knn Shapley values has been conducted, which demonstrates the associated potential threats such as the possibility to perform a membership inference attack. Several arguments are also provided to explain why making a differentially-private version of the knn Shapley values is not a trivial task. \n\nA variant of knn Shapley, called threshold-based knn (tknn), is introduced that focuses on the neighbourhood around a point according to a specified threshold to compute the Shapley value of this point. The benefits of this approach is terms of robustness and computation efficiency are clearly highlighted and supported by the results of the experiments conducted.\n\nFinally another contribution is the design of a differentially-private variant of tknn. This approach is elegant in the sense that it exploits the structure of tknn to bound the sensitivity and thus the noise that needs to be added to achieve (\\epsilon,\\delta)-privacy. \n\nA thorough set of experiments has been performed on a variety of different datasets against various baselines corresponding to variants of knn Shapley. The results demonstrate clearly that both the non-private and differentially-private versions of tknn-Shapley outperform the knn-shapley method or offer similar utility but at a lower cost.", "weaknesses": "The paper currently lacks a discussion on the limitations of the knn Shapley values compared to other methods for computing Shapley values in a more generic context. For instance, is there situations in which knn Shapley values are known not to be informative such as high-dimensional data?\n\nThe notions of collusion resistance and joint differential privacy should be defined in more depth. In particular, it would important to discuss how they differ from traditional differential privacy and whether or not this is a property that a lot of differential-privacy methods based on perturbations of counts could have.\n\nWith respect to analyzing the privacy risks associated to Shapley values, the paper is currently missing an important work from CCS last year that had conducted an in-depth study on the privacy risks related to the disclosure of Shapley values : \nLuo, X., Jiang, Y., & Xiao, X. (2022, November). Feature inference attack on shapley values. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (pp. 2233-2247).\nIt is important that the authors position their works with respect to this work. In particular, it would be great if the authors could comment on whether or not the attacks described in this paper could applied even against Shapley values computed with DP-tknn. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very positive feedback!\n\n**Q1. [Limitation of KNN-Shapley?]** *“The paper currently lacks a discussion on the limitations of the knn Shapley values compared to other methods for computing Shapley values in a more generic context. For instance, is there situations in which knn Shapley values are known not to be informative such as high-dimensional data?”* \n\n**A:** We appreciate the insightful question. Indeed, in comparison to the line of works of Data Shapley/Banzhaf, KNN-Shapley may have the following limitations:\n\n**(1)** KNN-Shapley focuses on KNN classifiers. As a result, the applicability of KNN-Shapley scores as a proxy of data points' value with respect to other ML models may not be straightforward. However, it is noteworthy that KNN is asymptotically Bayes optimal, implying that KNN-Shapley scores can be justified as a proxy for the data's value relative to the best possible model, i.e., the Bayes classifier, under certain asymptotic conditions.\n\n**(2)** For high-dimensional data, such as images, KNN-Shapley requires a public model to first map the original data into data embeddings, and evaluates the value of these embeddings rather than the original data. While this is indeed a constraint in certain scenario, it is important to recognize that utilizing a publicly available foundation model to convert original data into embeddings, followed by the fine-tuning of the model's last layer, has become a common practice. Therefore, in many situations, it might be more desirable to evaluate the value of data embeddings instead of the original data. \n\n\n**Q2. [More discussion for collusion resistance and Joint differential privacy?]** *“The notions of collusion resistance and joint differential privacy should be defined in more depth. In particular, it would important to discuss how they differ from traditional differential privacy and whether or not this is a property that a lot of differential-privacy methods based on perturbations of counts could have.”* \n\n**A:** \n**(1) How Joint DP differ from traditional DP?** Traditional differential privacy (DP) is designed to safeguard the identities of **all** private individuals within a dataset. In contrast, joint differential privacy considers a mechanism that releases one piece of its output to each individuals in the dataset (aligns well with our data valuation setting where each data value score is released to the corresponding data owner). Joint DP requires the privacy guarantees of the i-th piece of output to other private individuals in the dataset except for the i-th individual’s data. In our data valuation scenario, one can think of it as “the data value score for $i$th data wonder does not need to protect the privacy of $i$th data owner itself”. In particular, joint DP preserves the privacy guarantee when multiple data owners collude with each other and try to infer the membership of the rest of the data owners. \n\n**(2) whether or not this is a property that a lot of differential-privacy methods based on perturbations of counts could have?** No. Our DP-TKNN-Shapley mechanism $M(D) := (\\hat \\phi_{z_1}(D_{-z_1}), \\ldots, \\hat \\phi_{z_N}(D_{-z_N}))$ satisfies JDP guarantee is **because of the special, post-processing-based computation algorithm we use**. Recall from Appendix E.2.1, to compute DP-TKNN-Shapley, we first calculate $\\hat C(D)$ and then, for each $z_i \\in D$, we compute $\\hat C(D_{-z_i})$ through the deterministic post-processing step outlined in Appendix E.2.1, where the post-processing for $\\hat C(D_{-z_i})$ only depends on $z_i$ itself. Hence, due to DP’s post-processing property, in Theorem 16 we show that the JDP guarantee for the overall mechanism $M(D)$ has the same privacy parameter as the one for “sub-mechanism” $M_i(D_{-z_i}) := \\hat \\phi_{z_i}(D_{-z_i})$. An intuitive way of thinking why $M(D)$ is collusion resistant is that because random noise is only applied once on $\\hat C(D)$, each post-processed $\\hat C(D_{-z_i})$ are privatized with the same random noise. Hence, even if multiple attackers collude and share the received noisy data value scores with each other, they are effectively only sharing the same random sample of $\\hat C(D)$, and cannot gain more information about $z_i$ other than that. As a comparison, if we naively privatize each “sub-mechanism” $M_i(D_{-z_i}) = \\hat \\phi_{z_i}(D_{-z_i})$ with independent random noise, then the attackers can gather more information by sharing its own random sample that contains information about $z_i$, and thus such an approach is not only less efficient, but also does not enjoy such powerful collusion resistance property. \n\n\n**Q3. [Related literature on feature inference attack on the Shapley value]** \n\n**A:** We thank the reviewer for referring relevant literature! We have added the discussion for this CCS work in Appendix A. The privacy risks studied in their paper and our work are different. Specifically, the attack proposed in this CCS work is against the Shapley value for feature attribution, while we study the privacy risks when using the Shapley value for data valuation. Regarding the question of *“whether or not the attacks described in this paper could applied even against Shapley values computed with DP-TKNN.”*, we would like to stress that it is not clear how to extend TKNN-Shapley for feature attribution, hence currently it’s not possible to evaluate the attack on DP-TKNN-Shapley. "}]

Author rebuttal:
We thank all of the reviewers for their detailed and valuable comments. We are glad that our work receives a majority of positive reviews. We considered the reviews carefully and modified our paper accordingly. We have answered other questions in the individual responses. Here’s our global response, which summarizes the additional experiments and background materials we have/will be added to the paper:

**Q1 (for Reviewer qAKo and Reviewer z2hx) [Additional experiments for the membership inference (MI) attack proposed in Appendix C.2.2]**

**A:** **Evaluate the proposed MI attack on (non-private) TKNN-Shapley:** We additionally conducted the experiment of the proposed MIA against (non-private) TKNN-Shapley (**see Table 4 in the Rebuttal’s pdf**). We follow the exact experiment setup as one described in Appendix C.2.2. Similar to the attack results on KNN-Shapley, our MI attack also achieves non-trivial performance (>0.6) for most of the datasets and choice of parameters. This shows that both KNN-Shapley and TKNN-Shapley serve as additional channels for leaking membership information of private data. 

**Evaluate the proposed MI attack on DP-TKNN-Shapley:** To directly demonstrate how DP-TKNN-Shapley can mitigate the privacy risk, we additionally conducted the experiment of evaluating the proposed MI attack on DP-TKNN-Shapley (**see Table 5 and 6 in the Rebuttal’s pdf**). We follow the exact experiment setup as the one described in Appendix C.2.2, and we evaluate the attack performance when $\varepsilon = 0.5$ (Table 5) and $\varepsilon = 1$ (Table 6) for DP-TKNN-Shapley. Compared with the result on non-private TKNN-Shapley, we can see that the overall attack performance drops to around 0.5 (the performance of random guess). The result shows that DP-TKNN-Shapley is indeed very effective against membership inference attacks.

We have incorporated these results into the paper. 

**Q2 (for Reviewer qAKo) [Additional experiments for the task of data removal]**

**A:** We additionally conducted the “point removal” experiment where we remove the data points that receive the lowest data value scores, then train the model on the remaining of the dataset and check whether the test accuracy is actually improved. Here, we remove at most 10% of the full dataset. In this case, the dataset diversity is not being affected a lot by removing bad training data points. The specific settings for the model architecture used in the experiment follow from [1]'s Appendix D.3.2, and the specific settings for the datasets follow from the mislabeled data detection experiment (Appendix F.3.1). **Figure 7 in the Rebuttal’s pdf** shows results on the private setting (where we use $\varepsilon=1$), and **Figure 8 in the Rebuttal’s pdf** shows results on the non-private setting. Similar to the results for mislabel/noisy data detection experiment, we observe that **(1)** DP-TKNN-Shapley significantly outperforms the naively privatized KNN-Shapley in terms of privacy-utility tradeoff; **(2)** even non-private TKNN-Shapley achieves comparable performance as the original KNN-Shapley in discerning data quality. 

[1] Wang, Jiachen T., and Ruoxi Jia. "Data banzhaf: A robust data valuation framework for machine learning." AISTATS 2023.

**Q3 (for Reviewer QHAC) [Additional experiments for setting a smaller $\delta$]**

**A:** We thank the reviewer for the concrete suggestion, and we have additionally conducted experiments on the full datasets of 2DPlanes, Phonome, and CPU datasets (of sizes around 40k, 5k, and 8k respectively) and use $\delta = 10^{-5}$. The experiment settings follow exactly the one described in Appendix F.3.1, and the results are shown in **Table 15 in Rebuttal’s PDF**. Similar to the result for the case of $\delta = 10^{-4}$, DP-TKNN-Shapley still achieves significantly better performance compared with the two baseline approaches. We have incorporated this experiment result into Appendix F.3. 

**Q4 (for Reviewer SBGb and QHAC) [Brief background for the privacy risks in releasing aggregated statistics]**

**A:** Since 1998, researchers have observed that a lot of seemingly benevolent aggregate statistics of a dataset can be used to reveal sensitive information about individuals [1]. A classic example is Netflix Prize fiasco, where the researchers show that an anonymized dataset can leak many sensitive information about individuals [2]. Irit and Nissim [3] proved that “revealing too many statistics too accurately leads to data privacy breach”. A great amount of discussion and practical realization of these privacy attacks on aggregated statistics can be found in [4]. In 2020, the US Census Bureau used these privacy attacks to justify their use of differential privacy.

KNN-Shapley score for an individual is one kind of aggregated statistics that depends on the rest of the dataset. Hence, KNN-Shapley score intrinsically reveals private information about the rest of the dataset (where we use membership inference attack as a concrete example in our paper). In addition, when users collude, their KNN-shapley values can be combined to make joint inferences about the rest of the dataset.

We will integrate this discussion into the paper to improve the readability of the privacy risks associated with data valuation techniques.

[1] Samarati, Pierangela, and Latanya Sweeney. "Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression." (1998).

[2] Narayanan, Arvind, and Vitaly Shmatikov. "How to break anonymity of the netflix prize dataset." (2006).

[3] Dinur, Irit, and Kobbi Nissim. "Revealing information while preserving privacy." Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 2003.

[4] Dwork, Cynthia, et al. "Exposed! a survey of attacks on private data." Annual Review of Statistics and Its Application (2017)


Meta-review: I have read all the materials of this paper including the manuscript, appendix, comments, and response. Based on collected information from all reviewers and my personal judgment, I can make the recommendation on this paper, acceptance. All reviewers and I championed this paper.

**Research Question**

This paper considers the data valuation problem from the privacy perspective, which is a novel and overlooked angle in this area. 

**Presentation**

The presentation is very clear with structured organizations and summarized roadmaps in each section.

**Challenges**

Before illustrating the research challenges, the authors provided two illustrating examples to demonstrate the risks of the current framework of Shaley values. Personally, the example in Figure 2 is not interesting to me. It is quite normal that the Shapley value will change with the nearby data point removed. Instead, the example of membership inference attack attracts me a lot, where I traced Appendix C for more details. I suggest the authors to put more content of this example in the main paper.

The authors clearly illustrated the challenges of extending the current framework of Shapley value for privacy protection in Line 200-215. I omitted my rephrase here. 

**Philosophy**

The philosophy to tackle two challenges in Line 200-215 is missing. The authors directly provided their solution TKNN-Shapley in Section 4. I am not sure whether the authors can feel there is a gap between Section 3 and Section 4. In another word, the authors need to first demonstrate how they aimed to solve the challenges, then provide their solutions later. 

**Technique**

The techniques and corresponding analyses make sense to me.

**Experiments**

The current results with the extra ones in the author response demonstrate the effectiveness of the proposed method in terms of both effectiveness and efficiency.
Decision: Accept (spotlight)