Source-linked AI summary
Efficient Coreset Selection via K-Nearest Neighbor Graphs
Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui
TL;DR
Large-scale coreset selection is hindered by the time and memory demands of dense distance or item-cluster structures. KNNG-CS instead uses sparse local neighborhoods to select representatives, achieving comparable accuracy with 2.3×–41.2× faster selection and 0.3%–7.5% baseline peak memory.
Problem
Existing greedy coreset methods use dense distance or item-cluster structures that impose high computational and storage costs on large datasets.
Method
KNNG-CS estimates local representativeness from distance-aware incoming-neighbor scores on a K-nearest neighbor graph and greedily selects locally nonredundant nodes.
Results
2.3×–41.2× speedups and 0.3%–7.5% peak memory yielded comparable accuracy to representative coreset selection methods across real-world datasets.
Takeaways & Limitations
KNNG-CS provides a lightweight coreset selection approach that preserves representative samples while avoiding quadratic distance structures.
Takeaways & Limitations
Exact KNN-graph construction costs O(n^2d), so KNNG-CS relies on approximate graphs that slightly sacrifice accuracy.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper frames coreset selection as a way to reduce training cost while preserving utility, then introduces KNNG-CS to model local representativeness with a sparse K-nearest neighbor graph. Experiments report comparable coreset quality with substantially lower selection time and peak memory than state-of-the-art methods.
- Motivation: Coreset selection replaces a large training set with a smaller subset that preserves training utility while reducing computation and memory consumption.Selection before training also allows the subset to be reused across training runs or hyperparameter settings.
- Gradient-approximation coresets: GA-based methods select at most M items to approximate the gradients of all training items using feature-space representativeness.The representative error measures total distance from each item to its nearest selected representative, enabling selection without prior model training.
- Limitations of prior methods: Existing greedy methods incur costly dense distance or cluster-bound structures, while CRAIG precomputes pairwise feature distances for candidate-benefit evaluation.The paper notes that exact optimization is NP-hard and that CRAIG’s distance-matrix construction requires O(n^2d) time.
- KNNG-CS: KNNG-CS builds an approximate K-nearest neighbor graph, scores nodes through distance-aware incoming-neighbor votes, and greedily selects representative nodes.The graph stores K local outgoing neighbors, so importance reflects how many samples regard a node as a close local neighbor.
- Results: 2.3–41.2× speedups and 0.3%–7.5% peak memory are reported for KNNG-CS relative to state-of-the-art methods while preserving coreset quality.The evaluation uses real-world datasets.
2 The KNNG-CS Method
KNNG-CS builds a compact K-nearest neighbor graph, scores nodes using neighborhood structure and distance-aware edge weights, and greedily selects a representative coreset. Its graph-based design avoids quadratic distance storage, with O(nK) space complexity when K is small.
- KNNG Construction: KNNG represents each feature vector as a node and connects it to its K nearest neighbors with directed edges.The graph captures similarity relationships among vectors through local neighborhoods.
- KNNG Construction: O(n^1.14d) is the time complexity for building an approximate KNNG, while its space complexity is O(nK).KGraph is used to construct the graph, with K set to 10 in the experiments.
- Distance-Aware Node Scoring: Node importance combines in-degree with distance-aware normalized closeness weights computed by a softmax over outgoing neighbors.The importance of each node is the sum of the probability weights assigned by its in-neighbors.
- Greedy Coreset Selection: KNNG-CS repeatedly selects the node with the largest importance value, adds it to the coreset, and removes it together with its in-neighbors.Removed in-neighbors are expected to choose the selected node as their representative, and the process continues until M items are selected or no nodes remain.
- Complexity Analysis: O(nK) is the space complexity of KNNG-CS, covering the graph, edge probabilities, and node-importance array.The method computes node importance once and uses one-pass greedy removal, avoiding repeated benefit recomputation.
3 Experiments
Across four real-world datasets, KNNG-CS achieves test accuracy comparable to Full, CRAIG, and FastCore while reducing coreset-selection cost and memory usage. Increasing the coreset size improves accuracy before stabilization, and KNNG-CS converges at a similar rate to Full with fewer iterations.
- Exp. 1: Overall Accuracy and Efficiency: KNNG-CS, CRAIG, and FastCore achieve test accuracy comparable to Full across the experiments.Full trains on the complete training set, while the other methods use selected coresets.
- Exp. 1: Overall Accuracy and Efficiency: 2-18x speedup is achieved by FastCore through cluster-level selection, while CRAIG is slowest because it computes a distance matrix before greedy selection.FastCore clusters data points into more than 10,000 clusters, whereas CRAIG assigns equal item probabilities and uses a greedy framework after distance computation.
- Exp. 1: Overall Accuracy and Efficiency: 0.3%, 0.9%, 0.8%, and 3.4% peak memory of CRAIG are required by KNNG-CS on the four datasets, respectively.KNNG-CS also requires 7.5%, 6.8%, 4.1%, and 6.3% peak memory of FastCore, respectively.
- Exp. 2: Effect of Coreset Size M: As M increases, KNNG-CS accuracy initially improves and then stabilizes, motivating M = 0.01 × n as a balance between coreset size and accuracy.The results indicate that a small coreset can achieve sufficiently good performance through precise gradient approximation.
- Exp. 3: Convergence Evaluation: KNNG-CS and Full converge at the same rate and stabilize near optimal test accuracy, but KNNG-CS needs fewer iterations because its coreset is smaller.For Brazil and Card, the convergence evaluation uses 100 epochs and tracks validation accuracy over iterations.
4 Conclusion
KNNG-CS is a lightweight GA-based coreset selection method that replaces dense distance structures with sparse KNNG neighborhoods. It combines distance-aware incoming-neighbor scores with one-pass redundancy-aware selection to preserve representative samples from dense local regions.
- Method: KNNG-CS uses sparse local neighborhood structures captured by a KNNG instead of dense pairwise distance or large item-cluster bound matrices.This design avoids materializing quadratic distance structures during coreset selection.
- Method: KNNG-CS aggregates distance-aware incoming-neighbor scores to estimate item importance from the KNNG.
- Method: One-pass redundancy-aware selection preserves representative samples from dense local regions.
GenAI Usage Disclosure
The authors used LLMs only to polish language, while they generated and verified all technical manuscript content themselves.
- GenAI Usage Disclosure: LLMs were used only for grammar correction, clarity improvement, and readability refinement.They did not generate technical ideas, algorithms, experiments, results, analyses, or conclusions.
- GenAI Usage Disclosure: The authors carefully reviewed and verified all manuscript content.