Efficient Coreset Selection via K-Nearest Neighbor Graphs

• URL: http://arxiv.org/abs/2608.16270v1
• Date: Mon, 17 Aug 2026 08:43:32 GMT
• Title: Efficient Coreset Selection via K-Nearest Neighbor Graphs
• Abstract summary: Coreset selection reduces the cost of model training by replacing a large training set with a small representative subset.<n>This paper proposes KNNG-CS, a lightweight coreset selection method based on a $K$-nearest neighbor graph.<n> Experiments on four real-world datasets show that KNNG-CS achieves accuracy comparable to representative gradient-approximation coreset methods.
• Score: 21.95291891763573
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Coreset selection reduces the cost of model training by replacing a large training set with a small representative subset. Existing gradient-approximation coreset methods such as CRAIG and cluster-based variants can preserve model accuracy. Still, their selection stages often rely on dense pairwise distances or large item-cluster bound matrices, leading to high time and memory costs on large datasets. This paper proposes KNNG-CS, a lightweight coreset selection method based on a $K$-nearest neighbor graph. KNNG-CS exploits local neighborhood structures to estimate the importance of each data item and greedily selects representative nodes without maintaining a quadratic distance matrix. The method requires only linear storage in the number of edges. Experiments on four real-world datasets show that KNNG-CS achieves accuracy comparable to representative gradient-approximation coreset methods, while reducing selection time by $2.3\times$-$41.2\times$ and peak memory to $0.3\%$-$7.5\%$ of the baselines.

Related papers

• EMS Coreset: An Efficient Expectation-Maximization Algorithm for Sinkhorn Coreset [4.297295761793895]
  Coresets distill large datasets into small, representative subsets for efficient downstream learning.<n>We introduce a scalable Sinkhorn coreset method that permits closed-form updates of the entropically regularized OT coupling by allowing non-uniform coreset weights.<n>We establish consistency of the selected measure and Lipschitz stability to data perturbations, providing accuracy and robustness guarantees.
  arXiv  Detail & Related papers  (2026-08-17T04:46:34Z)
• Adaptive $k$ Nearest Neighbors Classifier via Granular Ball Computing [60.23863579199315]
  The $k$-Nearest Neighbor(KNN) algorithm is widely used across various tasks.<n>In this paper, an adaptive and efficient KNN approach via granular-ball computing is proposed.
  arXiv  Detail & Related papers  (2026-08-13T07:39:46Z)
• GLOBE: Trajectory-Aligned Gradient Matching with Structured SparseOptimization for Coreset Selection [4.969458805037944]
  On-device training of deep neural networks is constrained by the computational and memory costs of large-scale datasets.<n>We propose GLOBE, a trajectory-aligned coreset selection framework that formulates sample selection as a globally optimized sparse weighting problem.
  arXiv  Detail & Related papers  (2026-08-03T09:01:29Z)
• CuBAS: Information Geometric Curvature-Based Adaptive Sampling for Supervised Classification [52.452902154360565]
  CuBAS is an information-geometric framework for adaptive data selection in supervised classification.<n>A labeled dataset can be viewed as a statistical manifold, on which local curvature, estimated via the ratio of second to first-order observed Fisher information, faithfully encodes the geometric complexity of the data distribution.
  arXiv  Detail & Related papers  (2026-07-03T09:36:02Z)
• Active Learning with Low-Rank Structure for Data Selection [85.43185363043362]
  We introduce a new data selection framework based on low-rank approximation and residual-based sampling.<n>We show that it is possible to select a weighted subset of $tildeOleft(k + frac1varepsilon2right)$ data points whose average loss approximates the average loss over the full dataset.
  arXiv  Detail & Related papers  (2026-06-14T22:29:59Z)
• Selecting Samples on Graphs: A Unified Dataset Pruning Framework for Lossless Training Acceleration [71.77541419885925]
  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.
  arXiv  Detail & Related papers  (2026-06-11T05:13:32Z)
• Zero-Shot Coreset Selection: Efficient Pruning for Unlabeled Data [22.45812577928658]
  Coreset selection aims to find a representative subset of data to train models. ZCore is a method that efficiently selects coresets without ground truth labels or training on candidate data. We evaluate ZCore on four datasets and outperform several state-of-the-art label-based methods.
  arXiv  Detail & Related papers  (2024-11-22T21:17:49Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  We introduce a new adaptive $k$-nearest neighbours ($kK$-NN) algorithm that explores the local curvature at a sample to adaptively defining the neighborhood size. Results on many real-world datasets indicate that the new $kK$-NN algorithm yields superior balanced accuracy compared to the established $k$-NN method.
  arXiv  Detail & Related papers  (2024-09-08T13:08:45Z)
• Minimally Supervised Learning using Topological Projections in Self-Organizing Maps [55.31182147885694]
  We introduce a semi-supervised learning approach based on topological projections in self-organizing maps (SOMs) Our proposed method first trains SOMs on unlabeled data and then a minimal number of available labeled data points are assigned to key best matching units (BMU) Our results indicate that the proposed minimally supervised model significantly outperforms traditional regression techniques.
  arXiv  Detail & Related papers  (2024-01-12T22:51:48Z)
• Refined Coreset Selection: Towards Minimal Coreset Size under Model Performance Constraints [69.27190330994635]
  Coreset selection is powerful in reducing computational costs and accelerating data processing for deep learning algorithms. We propose an innovative method, which maintains optimization priority order over the model performance and coreset size. Empirically, extensive experiments confirm its superiority, often yielding better model performance with smaller coreset sizes.
  arXiv  Detail & Related papers  (2023-11-15T03:43:04Z)
• Coverage-centric Coreset Selection for High Pruning Rates [11.18635356469467]
  One-shot coreset selection aims to select a subset of the training data, given a pruning rate, that can achieve high accuracy for models that are subsequently trained only with that subset. State-of-the-art coreset selection methods typically assign an importance score to each example and select the most important examples to form a coreset. But at high pruning rates, they have been found to suffer a catastrophic accuracy drop, performing worse than even random coreset selection.
  arXiv  Detail & Related papers  (2022-10-28T00:14:00Z)
• Index $t$-SNE: Tracking Dynamics of High-Dimensional Datasets with Coherent Embeddings [1.7188280334580195]
  This paper presents a methodology to reuse an embedding to create a new one, where cluster positions are preserved. The proposed algorithm has the same complexity as the original $t$-SNE to embed new items, and a lower one when considering the embedding of a dataset sliced into sub-pieces.
  arXiv  Detail & Related papers  (2021-09-22T06:45:37Z)

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.