Research map / Graph learning / Graph self-supervised learning
Structural-Entropy-Based Sample Selection for Efficient and Effective Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SES, a sample selection method that decomposes graph structural entropy to node level via the Shapley value (linear-time reformulation) and combines it with training difficulty and importance-biased blue noise sampling.
Problem
Existing sample selection methods rely on local information (training difficulty, node degree) and ignore global graph connectivity patterns, leading to suboptimal selection under data budgets in supervised, active, and continual learning.
Approach
Decompose graph-level structural entropy to individual nodes using the Shapley value, reformulated to be computable in linear time in the number of edges, yielding a node-level structural entropy score; combine it with training difficulty and select diverse samples via importance-biased blue noise sampling on a kNN sample graph.
Key results
- On ImageNet-1K supervised learning at 1% sampling, SES reaches 13.43% vs. 11.49% for the best baseline (GraphCut).
- On CC SBU Align at 1% sampling, SES achieves 27.61 vs. 26.54 for the runner-up, and it is best across all sampling rates.
- In continual learning (class-incremental), SES is best on all five datasets, e.g., 68.26 on Split CIFAR10 at memory 100 vs. 64.54 for D^2 Pruning.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| combine structural entropy and training difficulty, then use importance-biased blue noise sampling (ablation) | sample selection · CIFAR10 supervised learning, average across sampling rates | accuracy: 62.63 -> 75.42 | Helped |
| add structural entropy scoring to training difficulty with highest-score selection (ablation) | CIFAR10 sample selection · CIFAR10 supervised learning, average across sampling rates | accuracy: 62.63 -> 67.67 | Helped |
| replace highest-score selection with blue noise sampling (ablation) | training-difficulty scoring · CIFAR10 supervised learning, average across sampling rates | accuracy: 62.63 -> 74.43 | Helped |
| replace highest-score selection with message passing (ablation) | training-difficulty scoring · CIFAR10 supervised learning, average across sampling rates | accuracy: 62.63 -> 73.01 | Helped |
| add structural entropy scoring to training difficulty with message passing (ablation) | CIFAR10 sample selection · CIFAR10 supervised learning, average across sampling rates | accuracy: 73.01 -> 75.22 | Helped |
| add structural entropy scoring to training difficulty with blue noise sampling (ablation) | CIFAR10 sample selection · CIFAR10 supervised learning, average across sampling rates | accuracy: 74.43 -> 75.42 | Helped |
| use blue noise sampling instead of message passing (ablation) | structural-entropy plus training-difficulty scoring · CIFAR10 supervised learning | accuracy: 75.22 -> 75.42 | No clear effect |
| select samples with SES rather than the strongest listed baseline | sample selection · ImageNet-1K supervised, 1% | accuracy: 11.49 -> 13.43 | Helped |
| select samples with SES rather than the strongest listed baseline | sample selection · ANLI, 1% | accuracy: 36.82 -> 38.16 | Helped |
| select samples with SES rather than the strongest listed baseline | sample selection · PASCAL VOC, 1% | mAP: 10.75 -> 16.15 | Helped |
| select samples with SES rather than Random | unlabeled sample selection · ImageNet-1K active learning, 1% | accuracy: 5.41 -> 6.69 | Helped |
| select replay samples with SES rather than the strongest listed baseline | continual learning replay memory · Split CIFAR10, memory 200 | average accuracy: 66.08 -> 69.32 | Helped |
Surprising findings
- Reducing the sampling rate to 10% in MiniGPT-4 fine-tuning yields 10x speedup with only 0.3% accuracy drop, suggesting text and VQA fine-tuning is insensitive to sampling rate.
Limitations
- Relies on grid search over several hyperparameters (k, beta, gamma, blue noise threshold), adding computational cost.
- Multimodal support and embedding quality (CLIP, Sentence-BERT) are identified as areas for improvement.
- Theoretical coverage bound relies on assumptions and is validated empirically only on a synthetic Gaussian mixture.
Experimental setup
Datasets: CIFAR10 CIFAR100 ImageNet-1K ANLI IMDB Review PASCAL VOC CC SBU Align Permuted MNIST Split MNIST Split CIFAR10 Split CIFAR100 Split Tiny-ImageNet
Benchmarks: CIFAR10 CIFAR100 ImageNet-1K ANLI IMDB Review PASCAL VOC CC SBU Align OKVQA IconVQA DocVQA GQA ScienceQA
Metrics: accuracy mAP average accuracy
Baselines: Random Moderate coreset CCS D^2 Pruning GraphCut Entropy Forgetting EL2N AUM Variance k-means k-DPP
Builds on: D^2 Pruning Shapley value structural entropy AUM CCS
Closest papers by meaning
- Towards a statistical theory of data selection under weak supervision (ICLR 2024 · similarity 0.87)
- Structural Entropy Guided Unsupervised Graph Out-Of-Distribution Detection (AAAI 2025 · similarity 0.87)
- Mitigating Label Noise on Graphs via Topological Sample Selection (ICML 2024 · similarity 0.87)
- Structural Entropy Based Graph Structure Learning for Node Classification (AAAI 2024 · similarity 0.87)
- Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond (ICML 2024 · similarity 0.86)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.