Localized Data Shapley: Accelerating Valuation for Nearest Neighbor Algorithms

We thank the reviewer for the time and effort in reviewing our paper. We answer your questions below.

Q1: Could you provide some practical guidance on estimating $k^*$ or choosing $n_L$ for a new dataset where the clustering structure is unknown?

A1: Deciding the number of landmarks $n_L$, or in general, the number of clusters $k^*$ for geometric clustering, is a long-standing challenging problem. What we did in Section 6.1 is essentially the most popular heuristic for this problem, which is also known as the Elbow method. That is, to test the metric of interest (e.g., the clustering error or running time in our context) with varying $n_L$, and choose the $n_L$ that gives the best performance.

Q2: In line 217, you mention that $\tau_{D_{mark}} \le \tau$ is "easily achieved by continuing the iterative process of FFT." How many landmarks does this typically require in practice? Does this ever result in $n_L > k^*$?

A2: Unfortunately, it is unlikely that we can find the optimal value of $k^*$ for general datasets. We do test the number of landmarks $n_L$ by running the FFT algorithm on the datasets in our experiments. We found that typically it takes up to hundreds of landmarks to achieve $\tau_{D_{mark}} \le \tau$ for a small $\tau$. This may result in a larger overhead in practice. Thus, in practice, we recommend using the Elbow method (see Figure 1) to fix some small number of landmarks.

We thank the reviewer for the time and effort in reviewing our paper. We answer your questions below.

Q1: Are there known scenarios where perturbation resilience does not hold? If so, does your method still outperform the baseline in those cases?

A1: Yes, perturbation resilience fails in scenarios such as (1) datasets with overlapping clusters where small perturbations can change cluster assignments, (2) high-dimensional data (i.e., curse of dimensionality) where distance-based clustering becomes ineffective, and (3) datasets with insufficient separation between clusters. However, even in these cases, our method still outperforms the baseline, though inevitably with a smaller speed-up. For example, see the results on high-dimensional datasets like CIFAR-10 and EMNIST in our experiments. Note that our worst-case complexity equals the baseline with negligible preprocessing overhead.

Q2: You report improvements in execution time, but do not present any accuracy comparisons. How accurate is your method in approximating the Shapley values compared to the baseline?

A2: We have added additional experiments about the accuracy of a popular downstream task. The short answer is that there is little difference between the accuracy of our method and that of the baseline kNN-Shapley. We refer the reviewer to our answer to reviewer WTuj for more details.

Q3: How does your method perform against other state-of-the-art data valuation techniques—both in terms of computation time and accuracy?

A3: The main focus of the paper is to accelerate the computation of kNN-Shapley, and to make the first attempt to address its scalability issue with respect to the number of test examples. We hope to stick to this goal and provide more focused comparisons for our purpose. The accuracy of our method is almost identical to the baseline kNN-Shapley, which should be unsurprising given their similar formulations. We refer readers to for example, the reference [19] for more comprehensive comparisons with other state-of-the-art data valuation techniques.

We thank the reviewer for the time and effort in reviewing our paper. We answer your questions below.

Q1: Compare with TKNN-Shapley in terms of compute efficiency, and evaluate the utility of proposed data values on popular downstream tasks.

A1: First of all, we believe it is more suitable to call this method "TNN-Shapley" instead of "TKNN-Shapley", which highlights that fact that it does not require a parameter $K$. Basically, TNN does not perform any ranking over the neighbors of the test point, which is why it only cost $O(n)$ time instead of $O(n \log n)$ time. It fetches all neighbors that are within the radius $\tau$ (in $O(n)$ time) and derives a value from the counts of these neighbors in each class. Thus, it should not be surprising that it tends to result in worse accuracy than methods with KNN formulations (see below).

We adopt the popular downstream task of mislabel detection, where 5% of the training points are randomly mislabeled, and we try to detect them using the data points with the lowest data values. We use the F1 score to evaluate the performance of valuation methods. The F1 score of our method is slightly worse than that of the un-thresholded kNN-Shapley (no more than 1% worse). The F1 score of TNN is 20-50% worse than the others in 9 out of 11 datasets. That is, if our F1 score is 70%, TNN's F1 score is at most 50%. We tune the radius $\tau$ on a validation set sampled from the noisy training set. We use the implementation of TNN by its authors.

In terms of efficiency, TNN is indeed faster than the baseline KNN-Shapley. The complexity of TNN is $O(n_{test} \cdot n_{train})$ instead of $O(n_{test} \cdot n_{train} \log n_{train})$, but still quadratic if the number of test points is large. Thus, it is slower than our method, especially over large datasets. For example, its running time is 5542.69 ($\pm$ 23.88) seconds for the Poker dataset, which is about 11$\times$ slower than ours.

We will add this comparison to the revised paper.

Q2: Discuss the online test query setting.

A2: Extending the technique to the online test query setting is an interesting and challenging direction. We are afraid that this challenge may be out of the scope of this paper, because online settings are significantly different from what we consider in the paper. However, the first idea that comes to mind is to resort to dynamic clustering techniques for our landmark building. Due to the time constraint, we are unable to dive deep into the investigation. We thank the reviewer for bringing up this interesting direction, and we will explore it in the future.

We hope that the reviewer will consider increasing the score.

We thank the reviewer for the time and effort in reviewing our paper. We answer your questions below.

Q1: In Table 1, each row corresponds to a different dataset. The baseline only has $\tau/d=0.05$ but Algorithm 1 has $\tau/d=0.05, 0.1, 0.2$. If you're going to vary $\tau/d$, it seems fair to also vary it for the baseline approach. Can you please run these experiments?

A1: We didn't vary the parameter $\tau$ for the baseline because the running time of the baseline is less sensitive to $\tau/d$. More specifically, the baseline has to go through all the training points for each test point, regardless of the radius value $\tau$. Thus, its running time is at least $O(n_{train} \cdot n_{test})$, which is quadratic if the number of test points is large. Due to the space limit, we fix the radius $\tau$ to be the smallest value for the baseline in our experiments, which gives it an advantage over our method but not the other way around. We are happy to run these experiments with varying $\tau$ for the baseline, and include them in the appendix of the revised paper.

Q2: Regarding your discussion after Theorem 4, let's imagine $n_{test} \approx n$, and let's assume that the partitions are roughly equally sized so that $s \approx n/n_L$ (you could make this formal under the right distributional assumption with some log factors). Ignoring log factors, your bound is $O(n_L nd + nn/n_L d)$. Optimizing over $n_L$, we would choose $n_L = \sqrt{n}$, then your bound is $O(n^{1.5} d)$. Would you present your result in this way? I think it makes the guarantee more digestible (with some mild assumptions), and makes it clear that you're getting a reasonable speedup $n^2$ to $n^{1.5}$.

A2: Sure, it sounds more logical to present the result in this way. We are happy to revise the paper accordingly. Thanks for the suggestion!

Q3: Could you run experiments where you plot baseline vs algorithm 1 performance by size of dataset? It's hard to tell from the raw numbers how the rate of the difference is changing. If a plot looks persuasive and you present your guarantee this way, I could change my opinion on the "marginal" impact of your work, and increase my score.

A3: It is true, and we should have done this to help the readers digest the result. Unfortunately, we are not allowed to present images or external links during the rebuttal process. We have plotted the running time of the baseline and our method by the size of dataset ($n_{train} \cdot n_{test}$). Basically, the baseline is represented by a straight line that scales linearly with the size, while our method has ups and downs depending on the difficulty of the datasets. The line of our method is far below the baseline, and scales sublinearly with the size.

We thank the reviewer for reviewing our paper and many constructive comments.

Q1: Table 1 suggests mixed results on CIFAR-10/EMNIST (512-D). Could you add a controlled sweep over dimensionality (e.g., random projections) to isolate the “curse of dimensionality” effect?

A1: We perform projections by a Gaussian random matrix on the CIFAR-10 dataset to reduce its dimensionality to 10, and use the same ratio of $\tau/d$ as before. The baseline takes 116s (148s previously) and our method with $\tau/d=0.05$ takes 13s (75s previously). The running time of all methods decreases, due to the smaller overhead for distance computation, but the ratio of the running time of the baseline to ours increases. It seems effective to reduce the dimensionality by random projections. We thank the reviewer for the suggestion, and will add this discussion to the revised paper.

Q2: Any practical heuristics for choosing τ in high dimensional spaces?

A2: We are not aware of any good strategies for choosing $\tau$ in high-dimensional spaces. A general approach to choose $\tau$ is to tune it on a validation set for the task at hand (e.g., classification accuracy). We report simple statistics of the tuned ratio $\tau/d$ for datasets in our experiments for your reference. The unsurprising rule is that a larger $\tau$ usually leads to better accuracy. However, the marginal gain of increasing $\tau/d$ saturates at $0.05$ for 3/8 of the datasets (all large datasets) and at $0.2$ for all.

Q3: The paper focuses on thresholded KNN; can the landmark-based trick extend to weighted or learned-metric KNN (cv. Wang & Jia ’24)? A short discussion or a negative result would help.

A3: It is an interesting question about extending the technique to [JW24]. As far as we know, they apply a very different dynamic programming (DP) technique to compute the kNN-Shapley values with respect to a "hard-label" utility function. Basically, they use DP to do counting of pivotal subsets for each data point. It seems possible to extend our technique to their setting by restricting the counting among data points whose distance to the test point is less than the radius $\tau$. We will explore this direction in the future, and thank you for your question.

Q4: How often does a real-world dataset satisfy the 3- (or 4-) perturbation-resilient k-center condition?

A4: Unfortunately, this condition rarely perfectly holds in real-world datasets. This is mostly due to the noise in the real-world data. For example, given two well-separated clusters with the majority of their data points satisfying the condition, there may be a small portion of outliers in each cluster that violate the condition. This is why we design the ball-expansion technique that searches for all data points within the radius $\tau$. It starts with the most likely data points and uses lightweight bounds to prune the search space, which allows it to adapt gracefully to the violations.

Q5: Could you include an empirical proxy (e.g., ratio of inter- to intra-cluster distances) or a stress-test that shows the algorithm’s degradation when the assumption is violated?

A5: We design a stress test with a random dataset. The dataset consists of two fixed centers surrounded by 5000 points each, which are created by sampling from a Gaussian distribution with the center being the mean. We gradually increase the variance to make the clusters less separated. Then, we run our method and monitor the change in its running time. It turns out that the running time of our method decreases. This is counter-intuitive to us at first sight. Later, we figure out that it can be beneficial to threshold-based KNN when the clusters become dispersed, as less points need to be considered during the landmark-based search. This is an interesting observation, and we thank the reviewer for the suggestion.