# Efficient Coreset Selection via K-Nearest Neighbor Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 14 references that are in the map.
- First posted on arXiv 17 Aug 2026.

## Builds on (most cited first, 5 of 5)

- [On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning](https://mlsanity.com/paper/1704.00805/) (2017)
- [Visualizing Large-scale and High-dimensional Data](https://mlsanity.com/paper/1602.00370/) (2016)
- [On Coresets for Support Vector Machines](https://mlsanity.com/paper/2002.06469/) (2020)
- [Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters](https://mlsanity.com/paper/1602.02151/) (2016)
- [Revisiting k-Nearest Neighbor Graph Construction on High-Dimensional Data : Experiments and Analyses](https://mlsanity.com/paper/2112.02234/) (2021)

## Built on by (most cited first, 1 of 1)

- [Round-Trip KNN Clustering: multiscale hierarchical cluster detection on directed nearest-neighbour graphs](https://mlsanity.com/paper/2610.06795/) (2026)

## Abstract (arXiv)

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×-41.2× and peak memory to 0.3%-7.5% of the baselines.