Efficient Coreset Selection via K-Nearest Neighbor Graphs
2026-08-17 • Machine Learning
Machine Learning
AI summaryⓘ
The authors propose KNNG-CS, a new method to pick a small but important subset of data to train machine learning models faster. Unlike older methods that need to compare every pair of data points, KNNG-CS uses a simpler graph of nearest neighbors to decide which data points matter most. This approach saves a lot of time and memory, especially on big datasets, while keeping the model's accuracy similar to older methods. Their tests on real-world data showed big improvements in speed and memory use.
coreset selectiongradient approximationK-nearest neighbor graphdata subset selectionmodel training efficiencymemory costalgorithm scalabilitygreedy selectionmachine learning
Authors
Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui
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.