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

• URL: http://arxiv.org/abs/2606.12913v1
• Date: Thu, 11 Jun 2026 05:13:32 GMT
• Title: Selecting Samples on Graphs: A Unified Dataset Pruning Framework for Lossless Training Acceleration
• Abstract summary: We present a unified graph-based DP framework.<n>By modeling the dataset as a weighted graph, DP can be cast as a Maximum Weight Clique Problem (MWCP)<n>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.
• Score: 71.77541419885925
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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.

Related papers

• Rethinking One-Shot Federated Graph Learning: Training-Free Statistical Estimation [12.66442044096499]
  One-shot federated graph learning generally aims to train Graph Neural Networks (GNNs) across clients with disconnected subgraphs in a single communication round.<n>Under extreme non-IID conditions, local GNN training suffers from severe cross-client representation misalignment.<n>We propose SPEAR, a training-free framework that directly computes topology-smoothed class prototypes from local graphs.
  arXiv  Detail & Related papers  (2026-09-05T15:55:22Z)
• Selectivity Drives Efficiency: Dataset Pruning for Visual Place Recognition [52.52131290631774]
  We propose a place-wise dataset pruning framework tailored for visual place recognition (VPR)<n>Our method treats each place as the basic pruning unit and introduces two novel metrics, i.e., intra-place diversity (IPD) and inter-place similarity (IPS)<n>Experiments demonstrate that our method consistently outperforms state-of-the-art DP baselines under different pruning ratios.
  arXiv  Detail & Related papers  (2026-07-16T12:16:00Z)
• OrderDP: A Theoretically Guaranteed Lossless Dynamic Data Pruning Framework [30.771327347534996]
  OrderDP aims to obtain stable, unbiased, and near-lossless training acceleration with theoretical guarantees.<n>We evaluate OrderDP against comprehensive baselines on CIFAR-10, CIFAR-100, and ImageNet-1K.
  arXiv  Detail & Related papers  (2026-06-07T11:11:51Z)
• UNSEEN: Enhancing Dataset Pruning from a Generalization Perspective [17.593940249922557]
  We propose a plug-and-play framework, UNSEEN, which can be integrated into existing dataset pruning methods.<n>We scale UNSEEN to multi-step scenarios and propose an incremental selection technique through scoring models trained on varying coresets.<n>Our method significantly outperforms existing state-of-the-art (SOTA) methods on CIFAR-10, CIFAR-100, and ImageNet-1K.
  arXiv  Detail & Related papers  (2025-11-17T05:17:39Z)
• Winning the Pruning Gamble: A Unified Approach to Joint Sample and Token Pruning for Efficient Supervised Fine-Tuning [71.30276778807068]
  We propose a unified framework that strategically coordinates sample pruning and token pruning.<n>Q-Tuning achieves a +38% average improvement over the full-data SFT baseline using only 12.5% of the original training data.
  arXiv  Detail & Related papers  (2025-09-28T13:27:38Z)
• Subsampling Graphs with GNN Performance Guarantees [34.32848091746629]
  We introduce new subsampling methods for graph datasets.<n>We prove that training a GNN on the subsampled data results in a bounded increase in loss compared to training on the full dataset.
  arXiv  Detail & Related papers  (2025-02-23T20:21:16Z)
• DispFormer: A Pretrained Transformer Incorporating Physical Constraints for Dispersion Curve Inversion [56.64622091009756]
  This study introduces DispFormer, a transformer-based neural network for $v_s$ profile inversion from Rayleigh-wave phase and group dispersion curves.<n>DispFormer processes dispersion data independently at each period, allowing it to handle varying lengths without requiring network modifications or strict alignment between training and testing datasets.
  arXiv  Detail & Related papers  (2025-01-08T09:08:24Z)
• SGM-PINN: Sampling Graphical Models for Faster Training of Physics-Informed Neural Networks [4.262342157729123]
  SGM-PINN is a graph-based importance sampling framework to improve the training efficacy of Physics-Informed Neural Networks (PINNs) Experiments demonstrate the advantages of the proposed framework, achieving $3times$ faster convergence compared to prior state-of-the-art sampling methods.
  arXiv  Detail & Related papers  (2024-07-10T04:31:50Z)
• Gradient-Free Structured Pruning with Unlabeled Data [57.999191898036706]
  We propose a gradient-free structured pruning framework that uses only unlabeled data. Up to 40% of the original FLOP count can be reduced with less than a 4% accuracy loss across all tasks considered.
  arXiv  Detail & Related papers  (2023-03-07T19:12:31Z)
• Boosting Differentiable Causal Discovery via Adaptive Sample Reweighting [62.23057729112182]
  Differentiable score-based causal discovery methods learn a directed acyclic graph from observational data. We propose a model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore.
  arXiv  Detail & Related papers  (2023-03-06T14:49:59Z)
• Attentional-Biased Stochastic Gradient Descent [74.49926199036481]
  We present a provable method (named ABSGD) for addressing the data imbalance or label noise problem in deep learning. Our method is a simple modification to momentum SGD where we assign an individual importance weight to each sample in the mini-batch. ABSGD is flexible enough to combine with other robust losses without any additional cost.
  arXiv  Detail & Related papers  (2020-12-13T03:41:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.