Training a large model requires how much data? The old answer was "the more, the better." But recent research increasingly shows that data quality matters far more than data quantity. One carefully selected good sample can be worth more than a hundred random ones.
So how do you pick the "most useful" subset from a million-scale training corpus?
This is essentially an optimization problem. The selected subset must satisfy two somewhat conflicting requirements: each sample should be high quality, but the selected samples should also be diverse—covered broadly, not just similar questions repeated.
A recent paper by Zhang, Guo, Pan, Liu, Zheng, Cheng, Keutzer, and Zhang (arXiv:2605.15691)—from a Chinese academic team—proposes a scheme that transforms data selection into a graph theory problem.
🌐 A Graph Theory Perspective
Imagine each training sample as a node. The node weight represents the sample's impact on training—for example, how much model performance on a validation set improves after training on it.
Then you compute the semantic similarity between every pair of samples. If two samples are too similar—like "What is a cat?" and "What's a cat?"—you connect them with an edge. In a good training subset, these two should not appear together, because their information is redundant.
Now the problem becomes: given this graph, select a set of nodes that minimizes edges among selected nodes (minimizing redundancy) while maximizing total weight (maximizing quality).
This is a classic graph theory problem: the maximum weight independent set. An independent set means no two selected nodes are connected by an edge.
> Maximum independent set is a classic NP-hard problem—exact solutions are impossible at million scale. But approximate methods, especially greedy or ranking-based heuristics, often work well in practice. SEED doesn't claim an exact solution; it uses the graph structure to define and solve the selection problem.
🔧 Two Improvements
SEED makes two refinements on top of this framework.
1. Node value calibration. Previous approaches assign node weights using a simple "influence score"—for example, gradient matching or influence functions. But these are vulnerable to gradient noise: a genuinely useful sample and a lucky one can be indistinguishable under a naive influence score. SEED restricts influence estimation to a "bidirectional salient subspace"—only considering gradient information in parameter directions that truly affect the task, ignoring noise directions.
2. Local scale normalization. When training data comes from multiple domains—say math problems and conversational data—semantic density can differ completely. Two similar math problems may be very close in embedding space, while two similar conversational sentences may be farther apart. A single global threshold for redundancy would over-filter dense domains and under-filter sparse ones. SEED adaptively adjusts each edge's threshold based on local neighborhood density.
📊 Results
Using SEED, they selected 200K high-quality multimodal training samples from a larger corpus, forming the Honeybee-Remake-SEED-200K dataset.
On instruction tuning, visual instruction tuning, and semantic segmentation, SEED consistently outperforms current state-of-the-art data selection methods. Notably, this isn't a result specific to one model—they validated across different model families.
🤷 Unclear Points
First, how is the "bidirectional salient subspace" determined? Is "salient" defined by gradient norms or some statistical test? If statistical, how is the significance threshold chosen? The paper claims the method separates signal from noise, but offers no actionable threshold-selection guidance.
Second, maximum weight independent set is NP-hard. How did they compute an approximate solution at million scale? What greedy algorithm or relaxation was used? How large is the gap between the approximate and exact solutions? The title and abstract don't discuss the solver.
Third, SEED's data subset has an elegant graph-theoretic interpretation, but is it overfitting to the validation set? If influence scores are computed against some validation set, the selected data may be path-dependently optimized for that distribution. SEED's generalization—whether selected data performs equally well on unseen validation sets—isn't directly discussed.
Still, reformulating data selection as a graph problem is a natural framework. Quality + diversity is, at its core, a weighted maximum independent set on a graph. Graph theory has worked underground for so many years—and now it surfaces again in data selection.
---
References
1. Zhang, Y., et al. (2026). *SEED: Targeted Data Selection by Weighted Independent Set*. arXiv:2605.15691 [cs.LG]. https://arxiv.org/abs/2605.15691 2. Toneva, M., et al. (2019). *An Empirical Study of Example Forgetting during Deep Neural Network Learning*. ICLR 2019. 3. Paul, M., et al. (2021). *Deep Learning on a Data Diet: Finding Important Examples Early in Training*. NeurIPS 2021. 4. Xia, M., et al. (2024). *Less Is More: Data Selection for Instruction Tuning*. ACL 2024. 5. Garey, M. R., & Johnson, D. S. (1979). *Computers and Intractability: A Guide to the Theory of NP-Completeness*. Freeman.