Research map / Graph learning / GNN architectures
$\mathbb{D}^2$ Pruning: Message Passing for Balancing Diversity & Difficulty in Data Pruning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes D^2 Pruning, a graph-based one-shot coreset selection method that combines example difficulty and data diversity via forward and reverse message passing over a k-NN dataset graph.
Problem
Coreset selection / data pruning methods either favor data diversity (leading to easy-sample-biased coresets) or difficulty scores (omitting easy samples needed for dense regions); these factors need to be jointly balanced.
Approach
Represent the dataset as a k-NN graph whose node features are difficulty scores; forward message passing propagates neighbors' difficulty scaled by RBF edge weights, and greedy selection followed by reverse message passing down-weights neighbors of selected samples to promote diversity.
Key results
- On CIFAR100 at 80% pruning, D^2 Pruning reaches 65.2% vs 64.0% for CCS; on ImageNet-1K at 50% and 80% it gains 1.0% and 1.4% over the previous best.
- On ANLI at 80% pruning, D^2 Pruning gets 44.5% vs 43.2% for CCS and 42.8% for random; on ImDB (2k) at 90% pruning it reaches 90.3% vs 87.5% for CCS.
- On DataComp filtering to 3.8M samples, D^2 Pruning (image+text) achieves 17.0 average vs 16.0 for reproduced CLIP-score filtering, with VTAB improving by about 1.2 points (18.2 vs 17.0).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use D² Pruning instead of the strongest listed baseline | CIFAR10 coreset selection · CIFAR10, 70% pruning | accuracy: 93.0 -> 93.3 | Helped |
| Use D² Pruning instead of the strongest listed baseline | CIFAR100 coreset selection · CIFAR100, 30% pruning | accuracy: 77.2 -> 78.2 | Helped |
| Use D² Pruning instead of the strongest listed baseline | CIFAR100 coreset selection · CIFAR100, 90% pruning | accuracy: 57.3 -> 56.9 | Hurt |
| Use D² Pruning instead of the strongest listed baseline | ImageNet-1K coreset selection · ImageNet-1K, 30% pruning | accuracy: 72.6 -> 72.9 | Helped |
| Use D² Pruning instead of the strongest listed baseline | ImageNet-1K coreset selection · ImageNet-1K, 90% pruning | accuracy: 57.3 -> 55.6 | Hurt |
| Use D² Pruning instead of the strongest listed baseline | ANLI coreset selection · ANLI, 70% pruning | accuracy: 44.5 -> 45.3 | Helped |
| Use D² Pruning instead of the strongest listed baseline | ANLI coreset selection · ANLI, 90% pruning | accuracy: 40.4 -> 40.3 | Hurt |
| Use D² Pruning instead of the strongest listed baseline | IMDB Reviews coreset selection · IMDB Reviews (2k), 90% pruning | accuracy: 89.5 -> 90.3 | Helped |
| Use CLIP image and text embeddings to compute sample distances rather than the reproduced CLIP-score filter | DataComp filtering · DataComp, 3.8M samples | Average accuracy: 16.0 -> 17.0 | Helped |
| Use image embeddings only for sample distances rather than image and text embeddings (ablation) | D² Pruning on DataComp · DataComp, 3.8M samples | Average accuracy: 17.0 -> 15.9 | Hurt |
| Use text embeddings only for sample distances rather than image and text embeddings (ablation) | D² Pruning on DataComp · DataComp, 3.8M samples | Average accuracy: 17.0 -> 16.6 | Hurt |
| Initialize node features with unit values instead of difficulty scores (ablation) | D² Pruning coreset selection · CIFAR10, 90% pruning | Coreset diversity and difficulty balance | Hurt |
Surprising findings
- Random pruning is hard to beat on ImageNet-1K at low pruning rates.
- Self-supervised prototypicality suffers drastically above 30% pruning, and self-supervised D^2 Pruning still falls short of random pruning.
Limitations
- Relies on a model trained on the full dataset to obtain difficulty scores and embeddings, which can carry model biases and prevents creating datasets from scratch.
- Gains are mainly at low-to-medium pruning rates; at 90% pruning CCS remains competitive or better on several settings.
- Hyperparameters k and gamma_r are swept per dataset and pruning rate on the test-set-reported runs, so selection of best configs is not strictly held out.
Experimental setup
Datasets: CIFAR10 CIFAR100 ImageNet-1K Adversarial NLI ImDB reviews (2k subset) DataComp (small)
Benchmarks: CIFAR10 CIFAR100 ImageNet-1K Adversarial NLI ImDB reviews DataComp (38 tasks: ImageNet, ImageNet dist. shift, VTAB, retrieval)
Metrics: accuracy zero-shot accuracy
Baselines: Random Entropy Forgetting EL2N AUM Moderate CCS CCS + k-Center BADGE Variance Prototypicality
Builds on: forgetting score CCS (coverage-based coreset selection) prototypicality message passing neural networks
Closest papers by meaning
- Data Pruning by Information Maximization (ICLR 2025 · similarity 0.92)
- GDeR: Safeguarding Efficiency, Balancing, and Robustness via Prototypical Graph Pruning (NeurIPS 2024 · similarity 0.89)
- Lightweight Dataset Pruning without Full Training via Example Difficulty and Prediction Uncertainty (ICML 2025 · similarity 0.89)
- Spanning Training Progress: Temporal Dual-Depth Scoring (TDDS) for Enhanced Dataset Pruning (CVPR 2024 · similarity 0.87)
- Exploring Learning Complexity for Efficient Downstream Dataset Pruning (ICLR 2025 · similarity 0.87)
- Rethinking Dataset Distillation for Classification: Do Distilled Sets Outperform Coresets? (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.