Search papers, labs, and topics across Lattice.
This paper introduces KNNG-CS, a novel coreset selection method that utilizes a K-nearest neighbor graph to efficiently identify representative data points for model training. By leveraging local neighborhood structures, KNNG-CS significantly reduces both selection time and memory usage compared to traditional gradient-approximation coreset methods, which often rely on dense pairwise distance computations. Experimental results demonstrate that KNNG-CS maintains comparable accuracy while achieving selection speed improvements of up to 41.2 times and memory reductions to as low as 0.3% of baseline methods.
KNNG-CS slashes selection time by up to 41.2 times while preserving model accuracy, revolutionizing coreset selection for large datasets.
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.
