TL;DR
Shapley-based data valuation is a powerful tool for quantifying data contributions, but its exponential computational cost makes it impractical when training data or evaluation tasks change dynamically. This paper introduces D-Shap, a framework that treats Shapley values as a persistent player-by-task matrix and leverages "model-induced locality" to perform fast, localized updates. D-Shap achieves millisecond-level task updates and up to a $1000\times$ speedup for data updates while maintaining high valuation accuracy.
What Problem Does This Paper Address?
In machine learning, data valuation helps us understand which training examples are most valuable for tasks like data pricing, dataset curation, and model debugging. The Shapley value is the gold standard for this, but computing it is notoriously expensive (#P-hard), often requiring training a model on exponentially many data subsets.
Worse still, real-world machine learning pipelines are dynamic: new evaluation tasks constantly appear, and new data contributors regularly expand the training set. Existing Shapley estimation methods are fundamentally static; they collapse fine-grained task-specific contributions into a single aggregated score per player. Consequently, whenever a new task or player arrives, the entire expensive computation must be rerun from scratch. This paper tackles the challenge of performing dynamic, incremental Shapley updates without global recomputation.
Methods
The core innovation of D-Shap is shifting the perspective of Shapley values from a one-shot aggregated score to a persistent player-by-task matrix ($\Phi$), where each entry records the contribution of a specific training instance (player) to a specific evaluation objective (task).
To maintain this matrix efficiently, D-Shap exploits model-induced locality—the insight that a model's performance on a given task usually depends only on a small subset of relevant training instances (e.g., nearest neighbors in KNN or local neighborhoods in Graph Neural Networks). This gives rise to two types of localized updates:
- Task-Incremental Updates (Utility Locality): When a new task arrives, D-Shap avoids retraining models by interpolating the new column from nearby existing columns. Crucially, instead of using raw feature proximity, it measures distance ($d_\Gamma$) based on the model's local computation structure (e.g., decision paths in trees or message-passing paths in GNNs).
- Player-Incremental Updates (Coalition Locality): When a new training instance is added, it only alters the local cooperative games of a small subset of tasks. D-Shap identifies these affected tasks and updates only their corresponding local matrix blocks, leaving the rest of the matrix frozen.
To bootstrap this matrix without requiring pre-specified external evaluation tasks, the authors introduce self-valuation. This technique treats each training player as a proxy task (using a leave-one-out approach). To make self-valuation scalable, they implement shared subset scheduling (reusing trained models across multiple tasks) and coverage-aware anchor selection (computing exact values only for a small set of representative "anchor" players and interpolating the rest).
Datasets
The authors evaluated D-Shap across five distinct model-dataset pairs, each representing a different type of model-induced locality:
- Weighted K-Nearest Neighbors (WKNN) on MNIST (neighbor-based locality)
- Decision Trees (DT) on Iris (partition-based locality)
- RBF Kernel SVM on Breast Cancer (kernel-relevance locality)
- Convolutional Neural Networks (CNN) on MNIST (representation-space locality)
- Graph Convolutional Networks (GCN) on Cora (graph neighborhood locality)
Key Insights and Ideas
- Preserving Fine-Grained Structure Enables Reuse: Moving from a scalar score per player to a player-by-task matrix prevents information loss, turning an exponential one-shot problem into a manageable matrix maintenance problem.
- Model Geometry over Feature Geometry: Feature similarity can be highly misleading for data valuation. For instance, two nodes in a GNN might have identical features but completely different graph neighborhoods, leading to entirely different data values. D-Shap's model-induced distance metric ($d_\Gamma$) successfully captures how the model actually uses the data.
- Data as its Own Workload: Self-valuation elegantly solves the cold-start problem by transforming the training set into a self-contained evaluation suite, ensuring the initialized matrix is well-aligned with the training data's intrinsic relationships.
Key Results
- Task-Incremental Speedups: D-Shap reduces per-task evaluation costs by $10^6$ to $10^8\times$, enabling real-time, millisecond-level updates while maintaining accuracy competitive with static baselines.
- Player-Incremental Speedups: For newly arriving data contributors, D-Shap cuts down update costs by $10^1$ to $10^3\times$ compared to standard recomputation methods.
- Efficient Matrix Construction: Shared subset scheduling and anchor selection deliver a $>25\times$ speedup in constructing the initial matrix. For deep models (CNNs and GNNs), where naive methods failed to finish within 100 hours, D-Shap successfully completed matrix construction in just a few hours.
Limitations and Future Work
- GNN Performance: While D-Shap consistently outperformed learning-based baselines on GNNs, its overall accuracy was lower on graph data than on tabular or image data. The authors note this is due to the inherent complexity of capturing multi-hop graph propagation within a simple distance metric ($d_\Gamma$).
- Fixed Encoders for Deep Models: For deep neural networks, the framework currently assumes that the feature encoder remains fixed during incremental updates to preserve a stable geometric space for interpolation. Extending D-Shap to handle continuously fine-tuned encoders remains an open challenge.
Summary updated