Pith. sign in

REVIEW 4 major objections 3 minor 1 cited by

This paper claims that Shapley-based data valuation can be made dramatically cheaper by exploiting model-induced locality: for each test point, only a small support set of training points influences the prediction, and exact Shapley computa

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-04 05:54 UTC pith:4B3ET5GV

load-bearing objection Solid subset-reuse algorithm, but the paper overclaims exact locality for retraining models and the concentration bound is off; worth a major-revision review. the 4 major comments →

arxiv 2603.03672 v2 pith:4B3ET5GV submitted 2026-03-04 cs.LG cs.AIcs.DBcs.GT

Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation

Xuan Yang , Hsi-Wen Chen , Ming-Syan Chen , Jian Pei This is my paper
classification cs.LG cs.AIcs.DBcs.GT
keywords data valuationShapley valuemodel-induced localitysupport setsubset reuseretraining costMonte Carlo estimationinformation-theoretic lower bound
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper claims that Shapley-based data valuation, normally exponential in the number of training points, can be made dramatically cheaper by exploiting a structural property of modern predictors: for a given test instance, only a small subset of training points influences the prediction. The authors formalize these support sets through the model's computational pathway, and show that when locality is exact, the Shapley value computed on the projected utility equals the global one; when approximate, the gap is bounded by the total influence of points outside the support. The central result is an information-theoretic lower bound: any correct algorithm must evaluate the model at least once for every distinct influential subset, and the proposed algorithm LSMR reaches that bound by training each distinct subset exactly once. A Monte Carlo variant LSMR-A keeps unbiasedness and exponential concentration while making runtime depend on the number of distinct sampled subsets rather than total draws. If correct, this turns data valuation from exhaustive coalition enumeration into a structured reuse problem.

Core claim

The paper's central claim is that Shapley data valuation can be projected onto support sets N(t) defined by the model's computational path (neighbors in KNN, leaves in trees, receptive fields in GNNs). Using the projected utility v_t^N(S)=v_t(S∩N(t)), the effective game collapses from 2^D to 2^{N(t)}, and when locality is exact this projected Shapley value equals the global Shapley value. The deeper discovery is subset-centric: a single evaluation of v_t(S) can update the Shapley values of all players via a closed-form weighted sum, and distinct subsets shared across test points need only be trained once. The paper proves an information-theoretic lower bound that any correct algorithm must t

What carries the argument

The central object is the model-induced support set N(t), a fixed set of training points that can influence the prediction at test point t through the model's computational graph. The projected utility v_t^N(S)=v_t(S∩N(t)) restricts the cooperative game to these supports. Lemma 2's subset-centric reformulation expresses each local Shapley value as a weighted sum over all subsets S of N(t), so one trained model per subset feeds all player updates. LSMR adds a bipartite support-mapping graph (N and R maps) with reverse-support indexing R_S = ∩_{z∈S} R(z) and pivot-based scheduling, which designates the first test point in a fixed ordering to train each subset, guaranteeing every distinct subse

Load-bearing premise

The entire construction relies on the support set N(t) staying fixed once computed from a full-data reference model, i.e., the prediction at t depends only on S∩N(t) for every retrained subset S; if retraining on S can pull points outside N(t) into the prediction pathway, the projected utility and exact-locality claim collapse.

What would settle it

Take a weighted KNN model on a real dataset, fix N(t) as its 2K neighbors, then for the subset S that deletes all of N(t) from the training set, retrain the model and evaluate at t. If v_t(S) differs from v_t(S∩N(t)) (e.g., the new nearest neighbor lies outside the original support), the exact-locality assumption fails for that S.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • If locality is exact (e.g., threshold KNN), Local Shapley is exactly the global Shapley value while requiring evaluation only over subsets of the support set.
  • Any correct algorithm needs at least |S| model trainings, where S is the family of distinct support-induced subsets, so LSMR's cost is information-theoretically optimal.
  • When support sets overlap across test points, the amortized number of trainings per test point shrinks as the test set grows; with finite-range supports it vanishes.
  • LSMR-A's unbiasedness and exponential concentration hold with the same sample complexity as classical Monte Carlo, but its retraining cost is governed by distinct sampled subsets rather than total samples.
  • Under distribution shift, classical Monte Carlo wastes draws on irrelevant points, while the local estimator structurally removes that variance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper's claims, the support-set abstraction could transfer to feature-attribution Shapley, where the same projection argument would cut the coalition space in linear models and tree ensembles.
  • The lower bound suggests a natural benchmark: measure |S| for a model and dataset directly, and any valuation algorithm faster than one training per distinct subset must be approximating a different game, not the exact local Shapley value.
  • A testable extension is to use the reference model's support sets as an active-learning criterion, prioritizing training points that belong to many test-point supports.
  • If support sets are re-estimated online as the training set changes, the reuse guarantees weaken; quantifying the drift on small datasets would show how much of the speedup survives outside the fixed-support assumption.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. The paper proposes Local Shapley, a data-valuation framework in which the utility of a training coalition is projected onto a support set N(t) derived from a reference model's computational pathway (Eq. 4). It claims that when locality is exact this projection preserves the Shapley value; it proves an information-theoretic lower bound on the number of retraining operations; and it introduces LSMR, an exact reuse algorithm, and LSMR-A, a Monte Carlo estimator, with experiments on WKNN, decision trees, RBF-SVM, and GNNs. The algorithmic machinery is clean and the reuse idea is appealing, but the central projection step is not valid for the retraining-based utility defined in Eq. (1). Since the paper's theoretical claims and experimental interpretations all depend on this step, the core contribution is not established.

Significance. If the projection were valid, the paper would make an important practical contribution: it would reduce Shapley-based data valuation from exponential enumeration over the full dataset to a subset-reuse problem governed by model-induced supports. The subset-centric reformulation (Lemma 2) and the pivot-based reuse scheduler (Section 4.3) are genuinely useful ideas for any cooperative game defined on a fixed support structure. However, the paper does not establish that the projected game equals, or even approximates, the standard retraining-based global game for the model families in the experiments. The information-theoretic lower bound is essentially a tautology as stated. Thus the practical speedups, while measured on a different target quantity, do not transfer to global Shapley values as claimed.

major comments (4)
  1. [Sec. 3.2, Eq. (4)] The projection v_t^N(S) = v_t(S ∩ N(t)) assumes that v_t(S), the utility after retraining on S, depends on S only through S ∩ N(t). This is false under the retraining definition Eq. (1). N(t) is fixed by a reference model trained on the full dataset, but when S omits points in N(t), points outside N(t) can become part of the computational pathway. For 1-NN, if the full-data nearest neighbor of t is a, but S = {b} with b outside N(t), the retrained model predicts from b, so v_t({b}) depends on b even though {b} ∩ N(t) = ∅. The same failure occurs for decision trees and RBF-SVM. The 'exact locality' claims in Remark 1 and the Abstract are therefore unsupported; at best they hold for a threshold-KNN utility, which is not the model used in the WKNN experiments.
  2. [Sec. 3.2, Assumption 1 / Prop. 1] Assumption 1 is not satisfied by the model families cited as approximate-locality examples. For KNN and trees, adding a non-support point can discontinuously change the prediction and hence the marginal contribution of a support point; no fixed additive constants ℓ_{t,z}(u) can bound such changes. The regularized-ERM example only covers smooth, strongly convex objectives, not KNN or decision trees. Consequently, Proposition 1 does not provide the promised approximation guarantee for the experiments in Section 6, and the correlation results in RQ1 are descriptive rather than evidence of the claimed bound.
  3. [Sec. 4.4, Theorem 1] Theorem 1 is a tautology rather than an information-theoretic lower bound. S is defined as the family of all subsets appearing in supports, and the theorem states that any algorithm computing {v_t(S)}_{t∈R_S} must evaluate v(S) for every S in S. This merely restates the output requirement; it does not show that computing Local Shapley values requires those evaluations, nor does it establish optimality of LSMR. Even if it were a valid lower bound for the projected game, it would not apply to the global retraining game because Eq. (4) changes the utility. The 'optimal reuse' claim for global Shapley therefore does not follow.
  4. [Sec. 5.2, Theorem 3] The Hoeffding bound is invalid as stated. With |v_t(S)| ≤ B, a single-round contribution in Algorithm 3 is (|N(t')|+1) v_t'(S)/|S| for z ∈ S (and the analogous expression for z ∉ S), which can be as large as (n+1)B when |S| = 1. The proof's claim that |X_m| ≤ B is therefore false. A correct concentration bound would depend on the support size n through the maximum importance weight, so the n-independent sample complexity in Corollary 2 is unsupported. This undermines the central statistical guarantee of LSMR-A.
minor comments (3)
  1. [Notation, Table 4] The projected utility is written v_t^N(S) in Section 3.2 but as \tilde v_t(S) in the Appendix notation table. Please unify.
  2. [Algorithm 3, lines 10-14] The terminology 'prefix-before-t subset S' is slightly confusing because S is defined from the position of t in a permutation of N(t) ∪ {t}. This is fine, but the text should clarify that the size of S is uniform on {0,...,|N(t)| }.
  3. [Sec. 6.2, RQ1] The correlation with Global-MC is not a valid fidelity test once Local Shapley is a different game. The correct check would be against the global Shapley of the original utility, not a correlation with an estimator of a different quantity. This framing should be revised.

Circularity Check

0 steps flagged

No significant circularity: the Local Shapley target is defined independently, and the reuse lower bound is a definitional accounting identity rather than a fitted or self-cited result.

full rationale

The paper's derivations are self-contained and do not reduce to their inputs by construction. Definition 1 defines Local Shapley from the projected utility in Eq. (4), and Lemma 1's reduction to the support set is the standard null-player property: points outside N(t) are null players, so the Shapley value of the restricted game equals the projected full-game value. Proposition 1's approximation bound follows from Assumption 1 with a probability-1/2 argument and does not presuppose the target bound. The information-theoretic lower bound in Theorem 1 is indeed tautological: S is defined in Eq. (11) as the family of subsets whose values are needed, so “any algorithm computing those values must evaluate v(S) at least once” follows directly from the oracle model described in the proof. That is an accounting identity, not a circular derivation; no fitted parameter is renamed as a prediction, and no load-bearing self-citation or imported uniqueness theorem is used. The empirical fidelity results (RQ1–RQ5) compare against an independently computed Global-MC baseline and do not fit constants to force agreement. The main risk is a correctness/soundness gap rather than circularity: the support set N(t) is fixed by a full-data reference model, and exact locality under retraining is questionable for ordinary KNN and decision trees, as the paper's own limitation passage acknowledges when it notes that nonconvex or globally coupled models may violate Assumption 1. This is a validity concern, not a circular step, so the circularity score is 0.

Axiom & Free-Parameter Ledger

5 free parameters · 5 axioms · 2 invented entities

The central theoretical claims rest on two unsupported premises: that support sets are coalition-invariant and that non-support influence is additively small. These are not derived from the model families and fail for the paper's own KNN example. The statistical guarantees also require a boundedness condition on per-sample contributions that the algorithm does not satisfy.

free parameters (5)
  • WKNN neighborhood K and support size 2K = K=5, |N(t)|=10
    Chosen by hand to define locality; fidelity/runtime trade-off is measured against this choice in Table 2.
  • RBF-SVM kernel threshold for support membership = 0.5
    Chosen by hand; controls which training points are in N(t).
  • GNN hop radius = L=2
    Chosen by hand to define the two-hop ego-network support set.
  • Decision tree min_samples_split / min_samples_leaf = not specified numerically
    Chosen by hand to control leaf/parent-node support size; exact values are not reported.
  • Monte Carlo stopping threshold tau = 0.05
    Chosen by hand in Eq. (14); determines convergence and all reported runtimes.
axioms (5)
  • domain assumption Assumption 1 (Additive Non-local Stability): non-support points affect marginal contributions only additively with small weights.
    Used to prove Proposition 1. It is not verified for the evaluated models and is violated for KNN when coalitions exclude the original support: outside points then become influential.
  • ad hoc to paper Support set N(t) is fixed by a reference model trained on the full dataset and does not depend on the coalition S.
    This is necessary for the projected utility in Eq. (4) to be a faithful proxy. It is stated in Sec. 3.2 but not proven and is false for standard KNN/tree retraining.
  • domain assumption Exact locality holds for KNN, trees, etc., so v_t(S)=v_t(S∩N(t)).
    Invoked in Remark 1 and Sec. 3.3. It holds for threshold-KNN with a fixed radius but not for fixed-K KNN or for retraining-based trees.
  • domain assumption Utility bound |v_t(S)|≤B for all t and S.
    Used in Theorem 3, but is insufficient: the estimator's per-sample weights are not bounded by B, so the resulting Hoeffding bound is invalid.
  • standard math Standard combinatorial identities, Hoeffding's inequality, law of total variance, and permutation-based Shapley characterization.
    Background math used in the proofs; these themselves are not the issue.
invented entities (2)
  • Support set N(t) no independent evidence
    purpose: Restricts Shapley computation to a per-test-point subset of training data.
    A modeling construct with no external falsifiable handle; its definition depends on the choice of model architecture and hyperparameters.
  • Local Shapley value under projected utility v^N_t no independent evidence
    purpose: New valuation target that ignores non-support training points.
    Defined by the authors; it is not an observable quantity independent of the paper's modeling choices, and it does not equal global Shapley unless exact locality holds for all coalitions.

pith-pipeline@v1.3.0-alltime-deepseek · 31354 in / 18530 out tokens · 195337 ms · 2026-08-04T05:54:10.372818+00:00 · methodology

0 comments
read the original abstract

The Shapley value provides a principled foundation for data valuation, but exact computation is #P-hard due to the exponential coalition space. Existing accelerations remain global and ignore a structural property of modern predictors: for a given test instance, only a small subset of training points influences the prediction. We formalize this model-induced locality through support sets defined by the model's computational pathway (e.g., neighbors in KNN, leaves in trees, receptive fields in GNNs), showing that Shapley computation can be projected onto these supports without loss when locality is exact. This reframes Shapley evaluation as a structured data processing problem over overlapping support-induced subset families rather than exhaustive coalition enumeration. We prove that the intrinsic complexity of Local Shapley is governed by the number of distinct influential subsets, establishing an information-theoretic lower bound on retraining operations. Guided by this result, we propose LSMR (Local Shapley via Model Reuse), an optimal subset-centric algorithm that trains each influential subset exactly once via support mapping and pivot scheduling. For larger supports, we develop LSMR-A, a reuse-aware Monte Carlo estimator that remains unbiased with exponential concentration, with runtime determined by the number of distinct sampled subsets rather than total draws. Experiments across multiple model families demonstrate substantial retraining reductions and speedups while preserving high valuation fidelity.

Figures

Figures reproduced from arXiv: 2603.03672 by Hsi-Wen Chen, Jian Pei, Ming-Syan Chen, Xuan Yang.

Figure 1
Figure 1. Figure 1: (a) Intra-support redundancy: the blue area denotes the support set N (𝑡). For training points 𝑧𝑖 and 𝑧𝑗 , many train￾ing subsets are shared in their Shapley value computations. (b) Inter-support redundancy: test points 𝑡𝑖 and 𝑡𝑗 have over￾lapping supports (darker blue). Within this overlap, subsets are shared across their Shapley computations. The yellow dotted subset illustrates one such shared training … view at source ↗
Figure 2
Figure 2. Figure 2: Scatter plots of Local Shapley (x-axis) versus Global Shapley (y-axis). Dashed lines indicate linear regression fits. [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Test accuracy versus the percentage of training data added in descending Shapley order. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Scalability with respect to the training set size [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Dynamic Shapley Computation

    cs.LG 2026-05 unverdicted novelty 6.0

    D-Shap reformulates dynamic Shapley valuation as structured matrix maintenance exploiting utility and coalition locality to support millisecond task updates and orders-of-magnitude cheaper player updates.

Reference graph

Works this paper leans on

65 extracted references · 3 linked inside Pith · cited by 1 Pith paper

  1. [1]

    S Basu, P Pope, and S Feizi. 2021. Influence Functions in Deep Learning Are Fragile. InInternational Conference on Learning Representations (ICLR)

    2021

  2. [2]

    Leo Breiman, Jerome Friedman, Richard A Olshen, and Charles J Stone. 1984. Classification and Regression Trees. Wadsworth International Group

    1984

  3. [3]

    Javier Castro, Daniel Gómez, and Juan Tejada. 2009. Polynomial calculation of the Shapley value based on sampling.Computers & Operations Research36, 5 (2009), 1726–1730

    2009

  4. [4]

    Hugh Chen, Ian C Covert, Scott M Lundberg, and Su-In Lee. 2023. Algorithms to estimate Shapley value feature attributions.Nature Machine Intelligence5, 6 (2023), 590–601

    2023

  5. [5]

    Lingjiao Chen, Paraschos Koutris, and Arun Kumar. 2019. Towards model-based pricing for machine learning in a data marketplace. InProceedings of the 2019 international conference on management of data. 1535–1552

    2019

  6. [6]

    Yi-Chung Chen, Hsi-Wen Chen, Shun-Gui Wang, and Ming-Syan Chen. 2023. Space: Single-round participant amalgamation for contribution evaluation in federated learning.Advances in Neural Information Processing Systems36 (2023), 6422–6441

    2023

  7. [7]

    Yan-Cheng Chen and Chao-Ton Su. 2016. Distance-based margin support vector machine for classification.Appl. Math. Comput.283 (2016), 141–152

    2016

  8. [8]

    Reynold Cheng, Lei Chen, Jinchuan Chen, and Xike Xie. 2009. Evaluating proba- bility threshold k-nearest-neighbor queries over uncertain data. InProceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. 672–683

    2009

  9. [9]

    Corinna Cortes and Vladimir Vapnik. 1995. Support-vector networks.Machine learning20, 3 (1995), 273–297

    1995

  10. [10]

    Thomas Cover and Peter Hart. 1967. Nearest neighbor pattern classification. IEEE transactions on information theory13, 1 (1967), 21–27

    1967

  11. [11]

    Xiaotie Deng and Christos H Papadimitriou. 1994. On the complexity of co- operative solution concepts.Mathematics of operations research19, 2 (1994), 257–266

    1994

  12. [12]

    S.A. Dudani. 1976. The distance-weighted k-nearest-neighbor rule.IEEE Trans- actions on Systems, Man, and CyberneticsSMC-6, 4 (1976), 325–327

    1976

  13. [13]

    Raul Castro Fernandez, Pranav Subramaniam, and Michael J Franklin. 2020. Data Market Platforms: Trading Data Assets to Solve Data Problems.Proceedings of the VLDB Endowment13, 11 (2020)

    2020

  14. [14]

    Ronald A. Fisher. 1936. The use of multiple measurements in taxonomic problems. Annals of Eugenics7, 2 (1936), 179–188. https://doi.org/10.1111/j.1469-1809.1936. tb02137.x

    arXiv 1936

  15. [15]

    Amirata Ghorbani and James Zou. 2019. Data shapley: Equitable valuation of data for machine learning. InInternational conference on machine learning. PMLR, 2242–2251

    2019

  16. [16]

    Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl

  17. [17]

    Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs.Advances in neural information processing systems30 (2017)

    2017

  18. [18]

    Zayd Hammoudeh and Daniel Lowd. 2024. Training data influence analysis and estimation: A survey.Machine Learning113, 5 (2024), 2351–2403

    2024

  19. [19]

    2009.The fourth paradigm: data-intensive scientific discovery

    Tony Hey, Stewart Tansley, Kristin Michele Tolle, et al. 2009.The fourth paradigm: data-intensive scientific discovery. Vol. 1. Microsoft research Redmond, WA

    2009

  20. [20]

    Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas Spanos, and Dawn Song. 2019. Efficient task-specific data valuation for nearest neighbor algorithms.Proceedings of the VLDB Endowment 12, 11 (2019), 1610–1623

    2019

  21. [21]

    Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J Spanos. 2019. Towards efficient data valuation based on the shapley value. InThe 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 1167–1176

    2019

  22. [22]

    Kevin Jiang, Weixin Liang, James Y Zou, and Yongchan Kwon. 2023. Opendataval: a unified benchmark for data valuation.Advances in Neural Information Processing Systems36 (2023), 28624–28647

    2023

  23. [23]

    Bojan Karlaš, David Dao, Matteo Interlandi, Sebastian Schelter, Wentao Wu, and Ce Zhang. 2023. Data debugging with shapley importance over machine learning pipelines. InThe Twelfth International Conference on Learning Representations

    2023

  24. [24]

    Thomas N Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. InInternational Conference on Learning Repre- sentations (ICLR)

    2017

  25. [25]

    Pang Wei Koh and Percy Liang. 2017. Understanding black-box predictions via influence functions. InInternational conference on machine learning. PMLR, 1885–1894

    2017

  26. [26]

    Yongchan Kwon and James Y Zou. 2022. WeightedSHAP: analyzing and improv- ing Shapley based feature attributions.Advances in Neural Information Processing Systems35 (2022), 34363–34376

    2022

  27. [27]

    David Lazer, Alex Pentland, Lada Adamic, Sinan Aral, Albert-László Barabási, Devon Brewer, Nicholas Christakis, Noshir Contractor, James Fowler, Myron Gutmann, Tony Jebara, Gary King, Michael Macy, Deb Roy, and Marshall Van Al- styne. 2009. Computational Social Science.Science323, 5915 (2009), 721–723. https://doi.org/10.1126/science.1167742

    doi:10.1126/science.1167742 2009

  28. [28]

    Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998. Gradient- based learning applied to document recognition.Proc. IEEE86, 11 (1998), 2278– 2324

    1998

  29. [29]

    Fan Liang, Wei Yu, Dou An, Qingyu Yang, Xinwen Fu, and Wei Zhao. 2018. A survey on big data market: Pricing, trading and protection.Ieee Access6 (2018), 15132–15154

    2018

  30. [30]

    Hong Lin, Shixin Wan, Zhongle Xie, Ke Chen, Meihui Zhang, Lidan Shou, and Gang Chen. 2025. A Comprehensive Study of Shapley Value in Data Analytics. Proceedings of the VLDB Endowment18, 9 (2025), 3077–3092

    2025

  31. [31]

    Jinkun Lin, Anqi Zhang, Mathias Lécuyer, Jinyang Li, Aurojit Panda, and Sid- dhartha Sen. 2022. Measuring the effect of training data on deep learning predictions via randomized experiments. InInternational Conference on Machine Learning. PMLR, 13468–13504

    2022

  32. [32]

    Jinfei Liu, Jian Lou, Junxu Liu, Li Xiong, Jian Pei, and Jimeng Sun. 2021. Dealer: An end-to-end model marketplace with differential privacy.Proceedings of the VLDB Endowment14, 6 (2021)

    2021

  33. [33]

    Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. 2020. From local explanations to global understanding with explainable AI for trees. Nature machine intelligence2, 1 (2020), 56–67

    2020

  34. [34]

    Xuan Luo, Jian Pei, Zicun Cong, and Cheng Xu. 2022. On shapley value in data assemblage under independent utility.Proceedings of the VLDB Endowment15, 11 (2022), 2761–2773

    2022

  35. [35]

    Xuan Luo, Jian Pei, Cheng Xu, Wenjie Zhang, and Jianliang Xu. 2024. Fast shapley value computation in data assemblage tasks as cooperative simple games. Proceedings of the ACM on Management of Data2, 1 (2024), 1–28

    2024

  36. [36]

    Julien Mairal, Jean Ponce, Guillermo Sapiro, Andrew Zisserman, and Francis Bach. 2008. Supervised dictionary learning.Advances in neural information processing systems21 (2008)

    2008

  37. [37]

    Sasan Maleki, Long Tran-Thanh, Greg Hines, Talal Rahwan, and Alex Rogers

  38. [38]

    Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore

  39. [39]

    Tomasz P Michalak, Karthik V Aadithya, Piotr L Szczepanski, Balaraman Ravin- dran, and Nicholas R Jennings. 2013. Efficient computation of the Shapley value for game-theoretic network centrality.Journal of Artificial Intelligence Research 46 (2013), 607–650

    2013

  40. [40]

    Elizbar A Nadaraya. 1964. On estimating regression.Theory of Probability & Its Applications9, 1 (1964), 141–142

    1964

  41. [41]

    Junyuan Pang, Jian Pei, Haocheng Xia, Xiang Li, and Jinfei Liu. 2025. Shap- ley value estimation based on differential matrix.Proceedings of the ACM on Management of Data3, 1 (2025), 1–28

    2025

  42. [42]

    Emanuel Parzen. 1962. On estimation of a probability density function and mode. The annals of mathematical statistics33, 3 (1962), 1065–1076

    1962

  43. [43]

    Jian Pei. 2020. A survey on data pricing: from economics to data science.IEEE Transactions on knowledge and Data Engineering34, 10 (2020), 4586–4608

    2020

  44. [44]

    Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. 2020. Estimating training data influence by tracing gradient descent.Advances in Neural Information Processing Systems33 (2020), 19920–19930

    2020

  45. [45]

    J Ross Quinlan. 2014.C4. 5: programs for machine learning. Elsevier

    2014

  46. [46]

    Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2016. Why Should I Trust You? Explaining the Predictions of Any Classifier. InKDD

    2016

  47. [47]

    Lloyd S Shapley. 1953. A value for n-Person Games: contributions to the Theory of Games (AM 28), Volume II. , 307–317 pages

    1953

  48. [48]

    Michelle Si and Jian Pei. 2024. Counterfactual Explanation of Shapley Value in Data Coalitions.Proceedings of the VLDB Endowment17, 11 (2024), 3332–3345

    2024

  49. [49]

    W. N. Street, W. H. Wolberg, and O. L. Mangasarian. 1993. Nuclear feature extraction for breast tumor diagnosis.IS&T/SPIE 1993 International Symposium on Electronic Imaging: Science and Technology1905 (1993), 861–870

    1993

  50. [50]

    Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. 2017. Re- visiting unreasonable effectiveness of data in deep learning era. InProceedings of the IEEE international conference on computer vision. 843–852

    2017

  51. [51]

    Qiheng Sun, Jiayao Zhang, Jinfei Liu, Li Xiong, Jian Pei, and Kui Ren. 2024. Shapley value approximation based on complementary contribution.IEEE Trans- actions on Knowledge and Data Engineering(2024)

    2024

  52. [52]

    Jiachen T Wang and Ruoxi Jia. 2023. Data banzhaf: A robust data valuation frame- work for machine learning. InInternational Conference on Artificial Intelligence and Statistics. PMLR, 6388–6421

    2023

  53. [53]

    Jiachen T Wang, Prateek Mittal, and Ruoxi Jia. 2024. Efficient data shapley for weighted nearest neighbor algorithms. InInternational Conference on Artificial Intelligence and Statistics. PMLR, 2557–2565

    2024

  54. [54]

    Jiachen T Wang, Prateek Mittal, Dawn Song, and Ruoxi Jia. 2024. Data shapley in one training run.arXiv preprint arXiv:2406.11011(2024). 13

    Pith/arXiv arXiv 2024

  55. [55]

    Jiachen T Wang, Tianji Yang, James Zou, Yongchan Kwon, and Ruoxi Jia. 2024. Re- thinking data shapley for data selection tasks: misleads and merits. InProceedings of the 41st International Conference on Machine Learning. 52033–52063

    2024

  56. [56]

    Wang, Yuqing Zhu, Yu-Xiang Wang, Ruoxi Jia, and Prateek Mittal

    Jiachen T. Wang, Yuqing Zhu, Yu-Xiang Wang, Ruoxi Jia, and Prateek Mittal

  57. [57]

    Kai Wei, Rishabh Iyer, and Jeff Bilmes. 2015. Submodularity in data subset selection and active learning. InInternational conference on machine learning. PMLR, 1954–1963

    2015

  58. [58]

    Jinghan Yang, Sarthak Jain, and Byron C Wallace. 2023. How Many and Which Training Points Would Need to be Removed to Flip this Prediction?. InProceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics. 2571–2584

    2023

  59. [59]

    Jinsung Yoon, Sercan Arik, and Tomas Pfister. 2020. Data valuation using re- inforcement learning. InInternational Conference on Machine Learning. PMLR, 10842–10851

    2020

  60. [60]

    Guangyi Zhang, Qiyu Liu, and Aristides Gionis. 2025. Shapley-Based Data Valu- ation for Weighted𝑘-Nearest Neighbors. InThe Thirty-ninth Annual Conference on Neural Information Processing Systems

    2025

  61. [61]

    Yansen Zhang, Xiaokun Zhang, Ziqiang Cui, and Chen Ma. 2025. Shapley value- driven data pruning for recommender systems. InProceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2. 3879–3888. 14 A Detailed Proofs A.1 Notations Symbol Meaning 𝑧∈D Training dataset (set of training points). 𝑡∈T Test set (set of test points). ...

    2025

  62. [2000]

    In Information Retrieval, Vol

    Automating the construction of internet portals with machine learning. In Information Retrieval, Vol. 3. Springer, 127–163

  63. [2013]

    Bounding the estimation error of sampling-based Shapley value approxi- mation.arXiv preprint arXiv:1306.4265(2013)

    Pith/arXiv arXiv 2013

  64. [2017]

    Neural Message Passing for Quantum Chemistry. InICML

  65. [2023]

    arXiv:2308.15709 [cs.LG] https://arxiv.org/abs/2308.15709

    Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation. arXiv:2308.15709 [cs.LG] https://arxiv.org/abs/2308.15709

    Pith/arXiv arXiv