From Points to Coalitions: Hierarchical Contrastive Shapley Values for Prioritizing Data Samples

AI summary

Overview

Research area: Data valuation and data-centric machine learning, grounded in cooperative game theory (Shapley values), representation learning, and hierarchical clustering.

Technical level: Advanced. The paper assumes familiarity with Shapley value axioms, Monte-Carlo permutation estimators, concentration inequalities, and contrastive embedding objectives.

Scope: The paper introduces Hierarchical Contrastive Data Valuation (HCDV), a three-stage framework that replaces point-wise Shapley computation with coarse-to-fine coalition games, and validates it across tabular, vision, streaming, OpenDataVal, augmentation-filtering, and data-marketplace settings.

What This Paper Is About

Assigning a fair value to each training example via Shapley values is principled but computationally brutal: exact computation costs O(n!), and treating every record as an isolated "player" ignores the geometric and semantic structure of real datasets. HCDV reframes the valuation game so that the players are multiscale, geometry-aware neighbourhoods rather than individual points, and value flows top-down from coarse coalitions to fine ones. The goal is to keep Shapley-style fairness guarantees while making valuation tractable at scales up to roughly 45 million samples.

Key Contributions

1. A scalable, geometry-aware valuation framework. HCDV combines (i) a contrastive, geometry-preserving encoder, (ii) a balanced coarse-to-fine hierarchy of clusters built with balanced k-means, and (iii) local Monte-Carlo Shapley games at each level whose budgets are propagated downward to children. The stated complexity collapses from O(n!) to O(T Σℓ Kℓ) = O(T K_max log n).

2. Axiomatic and statistical guarantees. The authors prove HCDV approximately satisfies the four Shapley axioms (efficiency, symmetry, dummy player, additivity) with surplus loss O(η log n), a sub-Gaussian coalition deviation bound of Õ(1/√T), and at most k·ε∞ regret for top-k selection.

3. Empirical validation across four benchmarks plus OpenDataVal. Experiments cover tabular (UCI Adult, n ≈ 48,842), vision (Fashion-MNIST, n = 70,000), synthetic (n = 3,000), and a 45M-sample Criteo-1B CTR task, plus the three released non-tabular OpenDataVal datasets.

4. Downstream task demonstrations. Valuation is applied directly to augmentation filtering, low-latency streaming updates, and fair marketplace payouts.

Main Findings

• Predictive utility gains from top-30% selection (Table 1). HCDV reaches 0.904 ± 0.002 AUC@30% on Synthetic, 0.844 ± 0.001 balanced accuracy on UCI Adult, 0.891 ± 0.001 test accuracy on Fashion-MNIST, and 0.6269 ± 0.0004 test AUC on Criteo-1B. MCDS scores 0.846, 0.828, and 0.879 on the first three and 0.6175 on Criteo-1B; GS scores 0.840, 0.819, 0.868, and 0.6142; Random scores 0.756, 0.759, 0.811, and 0.6021.

• Reported headline improvements. The paper states HCDV improves predictive utility by about +3–5 AUC on Synthetic and Criteo-1B, and by +1–3 balanced/test-accuracy points on UCI Adult and Fashion-MNIST, while reducing the point-wise coefficient of variation by 25–40% versus GS and MCDS. The abstract cites valuation-time reductions of up to 100×; the experimental section reports up to 14× faster than MCDS, 2–4× faster than GS, and 1.2–2× faster than Data Banzhaf on three datasets.

• Wall-clock cost (Table 2, single NVIDIA A100 40 GB and 32-core CPU). HCDV takes 340 s (Synthetic), 21 min (UCI Adult), 1.6 hr (Fashion-MNIST), and 12.3 hr (Criteo-1B), versus MCDS at 1,820 s, 94 min, 5.8 hr, and 47.5 hr. Data Banzhaf takes 670 s, 13 min, 1.9 hr, and 15.8 hr; Random takes 9 s, 5 min, 0.3 hr, and 0.8 hr.

• OpenDataVal results (Table 3). With I = 100 players per dataset, HCDV achieves the top result in every dataset–task–noise setting, improving by +1–3 pp macro-F1 on noisy label detection (NLD) and up to +0.03 absolute accuracy on dataset removal/adding (DR/DA) over the strongest baseline, DU-Shapley. On CIFAR10-embedding, HCDV's NLD scores are 0.16 (5% noise) and 0.33 (15% noise) versus DU-Shapley's 0.14 and 0.30; the gap widens at 15% corruption.

• Augmentation filtering. On Fashion-MNIST with 60k original images plus 10k augmented candidates (affine A₁, colour A₂, cutout A₃, and 2,500 Stable-Diffusion images A₄), selecting HCDV's top-1k augmentations boosts accuracy by +2.8 pp over bottom-1k and beats MCDS/GS by 0.9–1.2 pp at unchanged training time. 42% of selected samples land in previously unseen latent neighbourhoods, and HCDV achieves the highest class coverage (all 10 classes). Within the HCDV top-1k, 51% come from A₄, 23% from A₁, and only 7% from A₃ (cutout).

• Streaming valuation. On a 10-day click-stream task (1,500 sessions/day, d = 64 features, ≈15% positives, Wide&Deep model of 2×128 ReLU MLP plus sigmoid head), incremental HCDV preserves 99.6% of the predictive gain of full recomputation while cutting compute by 2.5×, with average update latency under two seconds (K₁=16, K₂=64, M=64, T=64, τ=0.35, rebalancing every m = 3 updates). Group-Shapley is reported to suffer both worse AUC and higher overhead.

• Marketplace fairness setup. Five non-overlapping UCI Adult subsets (n = 10,000 total; 1,950–2,100 points each) with different demographic profiles are used for revenue allocation, with leave-one-out retraining as the oracle. Seller p₂ is most influential (1.61 pp balanced-accuracy drop), followed by p₁ (1.42 pp), p₅ (1.18 pp), and p₄ (1.05 pp); the fifth seller's oracle contribution is not reported in the available text.

Methodology in Plain English

The approach runs in three stages. First, a neural encoder is trained so that examples with different labels are pushed apart in embedding space, while a smoothness regulariser prevents outliers from dominating. Second, the embedded data is recursively partitioned into a balanced k-means tree, splitting the dataset into K₁ clusters, then each cluster into more clusters, until every leaf holds at most M points. Third, value is assigned top-down: at each level, the clusters act as players in a small cooperative game whose payoff combines validation performance with contrastive dispersion. Because there are only a handful of clusters per level, Shapley values are estimated with T random permutations rather than exhaustively. The credit earned by a parent cluster is then divided among its children in proportion to their non-negative solo payoffs, which conserves total mass and keeps any efficiency error from growing beyond linear in tree depth. At the leaves, exact Shapley is computed if the leaf is small enough; otherwise the budget is split uniformly.

Why This Matters

Impact on research. The work challenges the default assumption that individual data points must be the atomic unit of valuation. By making coalitions the players, it opens a route to capturing synergies and geometric structure that point-wise Shapley methods cannot see, while retaining approximate axiomatic fairness. The finite-sample bounds—global efficiency deviation bounded by the sum of per-level Monte-Carlo errors plus leaf approximation error, and a 2k·ε∞ top-k regret guarantee—give practitioners a way to reason about selection quality.

Real-world applications:

• Data marketplace payouts, where sellers need compensation proportional to the incremental utility their slice adds to a shared model.
• Augmentation and data curation pipelines, filtering synthetic or generated samples to keep the ones that cover new latent regions rather than redundant ones.
• Streaming and online learning, where valuations must be refreshed incrementally as new batches arrive without rebuilding the hierarchy.
• Noisy-label detection and dataset editing, supported by the OpenDataVal NLD, DR, and DA evaluations.

Industry relevance. The paper's cost profile is the headline: HCDV runs in 12.3 hours on a 45M-sample Criteo-1B slice versus 47.5 hours for MCDS, and its streaming variant keeps update latency under two seconds, which is compatible with hourly or finer ingestion cadences. Sub-second-to-minutes valuation also makes the technique plausible for federated learning contribution accounting, active sampling, and recommender-system pipelines.

Future Directions

• Closing the gap between claimed and measured speedups. The abstract cites up to 100× time reduction, while the reported experiments show up to 14× versus MCDS; a fuller accounting across all settings would clarify where the larger factor applies.
• Sensitivity to hierarchy hyperparameters. Depth L, cluster counts Kℓ, leaf size M, permutation budget T, and the balance weights λ and α are all user-chosen. How robust the valuations are to these choices—and whether they can be adapted automatically—is not established.
• Extending beyond the demonstrated leaf rule. The uniform-split fallback introduces ε_leaf error when leaves exceed M; whether exact leaf Shapley or a better allocation rule remains affordable at very large M is an open design question.
• Broader marketplace evaluation. The fair-payout study uses five sellers and logistic regression on 10,000 UCI Adult points, with leave-one-out as the oracle. Whether the attribution remains fair under overlapping, adversarial, or strategically reported seller data is untested.

Target Audience

This paper is most useful to researchers and engineers working on data valuation, data-centric AI, and dataset curation; to practitioners building data marketplaces or contribution-accounting systems for federated learning; and to ML platform engineers who need Shapley-style attributions at scales where exact or flat Monte-Carlo methods are infeasible. Readers without background in cooperative game theory will find the theoretical sections demanding, but the experimental sections are readable on their own.

Authors’ abstract

How should we quantify the value of each training example when datasets are large, heterogeneous, and geometrically structured? Classical Data-Shapley answers in principle, but its O(n!) complexity and point-wise perspective are ill-suited to modern scales. We propose Hierarchical Contrastive Data Valuation (HCDV), a three-stage framework that (i) learns a contrastive, geometry-preserving representation, (ii) organizes the data into a balanced coarse-to-fine hierarchy of clusters, and (iii) assigns Shapley-style payoffs to coalitions via local Monte-Carlo games whose budgets are propagated downward. HCDV collapses the factorial burden to O(T sum_{l} K_{l}) = O(T K_max log n), rewards examples that sharpen decision boundaries, and regularizes outliers through curvature-based smoothness. We prove that HCDV approximately satisfies the four Shapley axioms with surplus loss O(eta log n), enjoys sub-Gaussian coalition deviation tilde O(1/sqrt{T}), and incurs at most k epsilon_infty regret for top-k selection. Experiments on four benchmarks--tabular, vision, streaming, and a 45M-sample CTR task--plus the OpenDataVal suite show that HCDV lifts accuracy by up to +5 pp, slashes valuation time by up to 100x, and directly supports tasks such as augmentation filtering, low-latency streaming updates, and fair marketplace payouts.