# Selecting Samples on Graphs: A Unified Dataset Pruning Framework for Lossless Training Acceleration

arXiv: https://arxiv.org/abs/2606.12913 · HTML: https://mlsanity.com/paper/2606.12913/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 53 references that are in the map.
- First posted on arXiv 11 Jun 2026.

## Builds on (most cited first, 30 of 37)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Segment Anything](https://mlsanity.com/paper/2304.02643/) (2023)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Mixed Precision Training](https://mlsanity.com/paper/1710.03740/) (2017)
- [AutoAugment: Learning Augmentation Policies from Data](https://mlsanity.com/paper/1805.09501/) (2018)
- [An Empirical Study of Example Forgetting during Deep Neural Network Learning](https://mlsanity.com/paper/1812.05159/) (2018)
- [Deep Learning on a Data Diet: Finding Important Examples Early in Training](https://mlsanity.com/paper/2107.07075/) (2021)
- [Beyond neural scaling laws: beating power law scaling via data pruning](https://mlsanity.com/paper/2206.14486/) (2022)
- [Dataset Condensation with Gradient Matching](https://mlsanity.com/paper/2006.05929/) (2020)
- [Dataset Distillation by Matching Training Trajectories](https://mlsanity.com/paper/2203.11932/) (2022)
- [Dataset Condensation with Distribution Matching](https://mlsanity.com/paper/2110.04181/) (2021)
- [Selection via Proxy: Efficient Data Selection for Deep Learning](https://mlsanity.com/paper/1906.11829/) (2019)
- [Not All Samples Are Created Equal: Deep Learning with Importance Sampling](https://mlsanity.com/paper/1803.00942/) (2018)
- [GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training](https://mlsanity.com/paper/2103.00123/) (2021)
- [Identifying Mislabeled Data using the Area Under the Margin Ranking](https://mlsanity.com/paper/2001.10528/) (2020)
- [Prioritized Training on Points that are Learnable, Worth Learning, and Not Yet Learnt](https://mlsanity.com/paper/2206.07137/) (2022)
- [Dataset Meta-Learning from Kernel Ridge-Regression](https://mlsanity.com/paper/2011.00050/) (2020)
- [GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning](https://mlsanity.com/paper/2012.10630/) (2020)
- [Dataset Pruning: Reducing Training Data by Examining Generalization Influence](https://mlsanity.com/paper/2205.09329/) (2022)
- [Online Batch Selection for Faster Training of Neural Networks](https://mlsanity.com/paper/1511.06343/) (2015)
- [Coverage-centric Coreset Selection for High Pruning Rates](https://mlsanity.com/paper/2210.15809/) (2022)
- [Accelerating Deep Learning by Focusing on the Biggest Losers](https://mlsanity.com/paper/1910.00762/) (2019)
- [InfoBatch: Lossless Training Speed Up by Unbiased Dynamic Data Pruning](https://mlsanity.com/paper/2303.04947/) (2023)
- [Data Pruning via Moving-one-Sample-out](https://mlsanity.com/paper/2310.14664/) (2023)
- [Large-scale Dataset Pruning with Dynamic Uncertainty](https://mlsanity.com/paper/2306.05175/) (2023)

## Abstract (arXiv)

The rapid growth of modern training datasets has significantly increased computational cost, motivating dataset pruning~(DP) methods which retain only a subset of informative samples to reduce training cost. Existing pruning criteria typically rely on either intrinsic signals that assess samples independently or extrinsic signals that promote diversity via pairwise relations. While effective in their own specific regimes, each captures only one aspect of sample utility and lacks robustness across different pruning ratios or data distribution. In this work, we present a unified graph-based DP framework. By modeling the dataset as a weighted graph, where node weights encode intrinsic value and edge weights encode extrinsic value, DP can be cast as a Maximum Weight Clique Problem (MWCP). Although MWCP is NP-hard, its structure admits a principled greedy solution based on sample-wise marginal gains. Under a few mild conditions, we further prove that this unified objective enjoys a formal approximation guarantee, which applies to a broad family of importance metrics and provides practical design guidelines. Extensive experiments show that our method outperforms existing DP methods while substantially reducing training cost, reducing training time by over 40% without sacrificing accuracy on ImageNet-1k with ResNet-50.