Search papers, labs, and topics across Lattice.
This paper introduces a unified graph-based framework for dataset pruning (DP) that optimally selects informative samples to accelerate training while minimizing computational costs. By modeling the dataset as a weighted graph, where node weights represent intrinsic value and edge weights signify extrinsic value, the authors reformulate DP as a Maximum Weight Clique Problem (MWCP) and provide a greedy solution with formal approximation guarantees. Extensive experiments demonstrate that this method reduces training time by over 40% on ImageNet-1k with ResNet-50, outperforming existing DP techniques without compromising accuracy.
A novel graph-based dataset pruning method achieves over 40% faster training on ImageNet-1k while maintaining accuracy, challenging the status quo of sample selection.
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.
