🤖 machine learning

Efficient Coreset Selection via K-Nearest Neighbor Graphs

This paper introduces KNNG-CS, a lightweight coreset selection method that leverages K-nearest neighbor graphs to efficiently identify representative data subsets with significantly reduced time and memory costs while maintaining accuracy comparable to existing gradient-approximation approaches.

Original authors: Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

Published 2026-08-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Machine learning models are the engines behind many modern tools, from recognizing faces in photos to predicting stock market trends. To learn how to do these tasks, these models need to be fed massive amounts of data. Imagine trying to teach a student by giving them every single book in a library; they would eventually learn, but the process would be incredibly slow and exhausting. In the world of artificial intelligence, this is the reality of training on huge datasets. It requires enormous computing power and memory, often making it too expensive or slow for many practical applications. To solve this, scientists use a technique called coreset selection. The goal is simple: instead of using the entire library, find a small, perfect subset of books that contains all the essential lessons. If you can train the model on this tiny, representative sample, it learns just as well as if it had read everything, but in a fraction of the time and with far less memory.

For years, the best ways to find these small, perfect subsets have relied on a method that is computationally heavy. These existing approaches try to measure the distance between every single data point and every other data point to see which ones are most similar. It is like trying to find the best representative for a crowd by having every person measure their distance to every other person in the room. While this works, it creates a massive amount of data that is difficult to store and process, especially when the dataset grows large. The researchers at Xidian University and their collaborators realized that this "measure everything" approach was inefficient. They observed that the most useful representatives in a dataset are usually those that sit in the middle of dense groups of similar items, rather than those standing alone. A sample that is close to many others is likely to represent a common pattern, while an isolated sample is less likely to be a good stand-in for a large group.

To address this, the team developed a new method called KNNG-CS. Instead of forcing every item to measure its distance to every other item, they built a map that only connects each item to its ten closest neighbors. This creates a sparse network, or a graph, that captures the local relationships between data points without the overwhelming burden of calculating every possible connection. Once this map is built, the researchers assigned a score to each item based on how many other items pointed to it as a neighbor and how close those neighbors were. Items that were frequently chosen as a close neighbor by many others received a high score, marking them as highly important representatives. The algorithm then greedily selected the highest-scoring items to form the final small subset. As each high-scoring item was chosen, the algorithm removed it and its neighbors from the pool, ensuring that the selected group covered the entire dataset efficiently without redundancy.

The results of this new approach were striking when tested on four real-world datasets, ranging from forest cover types to movie ratings and credit card defaults. The new method produced a small training set that allowed the machine learning model to achieve accuracy comparable to the best existing methods. However, the difference in efficiency was dramatic. The new method ran between 2.3 and 41.2 times faster than the previous leading techniques. Even more impressive was the reduction in memory usage. While older methods required storing massive tables of distances that could consume gigabytes of memory, the new approach used only 0.3% to 7.5% of that memory. In practical terms, this means that tasks which previously required expensive, high-end servers could now be performed on much smaller, more accessible machines. The researchers found that even with a very small subset of data, the model learned effectively, converging to a stable solution much faster than if it had been trained on the full dataset.

This work demonstrates that by focusing on local relationships rather than global comparisons, it is possible to drastically simplify the process of preparing data for machine learning. The study confirms that you do not need to calculate every possible distance to find the most important data points; a smart, local map is sufficient. By using this graph-based strategy, the researchers have shown that high-quality model training can be achieved with a fraction of the time and resources previously thought necessary. This opens the door for more efficient training processes, allowing complex models to be developed and deployed in environments where computing power is limited, without sacrificing the quality of the final result.

Technical Summary: Efficient Coreset Selection via K-Nearest Neighbor Graphs

Problem Statement

Coreset selection aims to reduce the computational and memory costs of training machine learning models by replacing a large training set with a small, representative subset. The paper focuses on gradient-approximation (GA) based coreset selection. In this framework, the goal is to select a subset $C$ of size $M$ from a training set $T$ such that the gradients of the full set are well-approximated by the subset. This problem is mathematically reduced to minimizing the feature-space representative error (Eq. 1), where every data point is represented by its nearest neighbor in the selected coreset.

Existing GA-based methods, such as CRAIG and FastCore, rely on greedy selection strategies. However, they face significant scalability issues:

CRAIG pre-computes a dense pairwise distance matrix, requiring $O(n^2)$ space and $O(n^2d)$ time, which becomes prohibitive on large datasets.
FastCore replaces item-item distances with item-cluster upper bounds to save space, but it often requires a massive number of clusters (hundreds to tens of thousands) to maintain accuracy, leading to considerable overhead in computing and storing large bound matrices.

The authors observe that feature-space representativeness is inherently local: a sample that serves as a close neighbor to many other samples is likely to represent a dense local region with low approximation error. Existing methods fail to exploit this locality efficiently because they rely on dense structures rather than sparse neighborhood relations.

Methodology: KNNG-CS

The paper proposes KNNG-CS, a lightweight coreset selection method based on a K-Nearest Neighbor Graph (KNNG). The method operates in three main stages:

1. Approximate KNNG Construction

Instead of computing all pairwise distances, the method builds an approximate KNNG $G=(V, E)$ over the feature vectors. Each node $x_i$ connects to its $K$ nearest neighbors.

Efficiency: Using state-of-the-art approximate methods (e.g., KGraph), the construction time is $O(n^{1.14}d)$ , and the space complexity is linear, $O(nK)$, where $K$ is a small constant (set to 10 in experiments). This avoids the quadratic space requirement of dense matrices.

2. Distance-Aware Node Scoring

The core innovation is a scoring function that estimates the importance of each node (data item) based on its local neighborhood structure within the KNNG.

In-Degree: A node with a high in-degree (many nodes point to it as a nearest neighbor) is a strong candidate for representativeness.
Distance Awareness: In-degree alone is insufficient. The method incorporates edge distances by converting them into probabilities using a softmax function (Eq. 2).
Scoring Formula: The importance score $P_i$ for a node $v_i$ is the sum of the softmax probabilities of all incoming edges (Eq. 3):
$P_i = \sum_{v_j \in N_{in}^G(v_i)} p_{ji}$
where $p_{ji}$ represents the normalized closeness weight from neighbor $v_j$ to $v_i$ . This allows the method to distinguish between nodes with equal in-degrees but different proximity to their neighbors.

3. Greedy Selection with Redundancy Removal

The selection process is a one-pass greedy algorithm:

Compute the importance score $P_i$ for all nodes.
Select the node with the highest score and add it to the coreset $C$ .
Redundancy Removal: Immediately remove the selected node and all its in-neighbors from the graph. The rationale is that if a node is selected, its in-neighbors (which regard it as a close neighbor) will be represented by it and do not need to be selected themselves.
Repeat until $M$ items are selected.

This approach avoids repeated benefit recomputation, a major bottleneck in traditional greedy methods.

Key Contributions

KNNG-CS Algorithm: A scalable, GA-based coreset selection method that utilizes a sparse K-Nearest Neighbor Graph to avoid expensive dense distance structures.
Novel Scoring Mechanism: A distance-aware incoming-neighbor scoring function that estimates local representativeness directly from the KNNG without storing dense pairwise distances.
Efficiency Gains: Empirical validation demonstrating that the method significantly reduces selection time and memory usage while maintaining coreset quality comparable to state-of-the-art methods.

Experimental Results

The authors evaluated KNNG-CS on four real-world datasets: CovType, IMDB, Brazil, and Card. They compared their method against Random sampling, CRAIG, and FastCore.

Effectiveness (Accuracy): KNNG-CS achieved test accuracy comparable to CRAIG and FastCore, and significantly better than Random sampling. While CRAIG showed slightly higher accuracy on some datasets (IMDB, Card, Brazil) due to its use of exact distances, KNNG-CS maintained competitive performance.
Efficiency (Time): KNNG-CS demonstrated substantial speedups:
- 2.3× to 41.2× faster than CRAIG.
- 2.3× to 4.9× faster than FastCore.
- The speedup is attributed to the efficient KNNG construction and the one-pass greedy strategy that avoids matrix computations.
Memory Usage: KNNG-CS drastically reduced peak memory consumption:
- Required only 0.3% to 3.4% of the peak memory used by CRAIG.
- Required only 4.1% to 7.5% of the peak memory used by FastCore.
- This is because KNNG-CS stores only $O(nK)$ edges, whereas competitors store $O(n^2)$ distance matrices or large item-cluster bound matrices.
Convergence: Training on the selected coreset converged much faster (in terms of iterations) than training on the full dataset, with the coreset size $M=0.01n$ providing a good balance between efficiency and effectiveness.

Significance and Claims

The paper claims that KNNG-CS offers a practical solution for large-scale coreset selection by shifting from dense, global distance structures to sparse, local neighborhood structures. By leveraging the inherent locality of feature spaces, the method achieves:

Linear storage complexity ($O(nK)$) compared to the quadratic complexity ( $O(n^2)$ ) of previous state-of-the-art methods.
Significant reductions in both time and memory costs without sacrificing the quality of the selected subset.
A lightweight selection process that requires only a single pass of greedy selection after graph construction, eliminating the need for repeated distance calculations.

The authors conclude that this approach enables efficient coreset selection for large datasets where traditional gradient-approximation methods are computationally or memory-prohibitive.