Structural-Entropy-Based Sample Selection for Efficient and Effective Learning

## Abstract

Abstract Sample selection improves the efficiency and effectiveness of machine learning models by providing informative and representative samples.
Typically, samples can be modeled as a sample graph, where nodes are samples and edges represent their similarities.
Most existing methods are based on local information, such as the training difficulty of samples,
thereby overlooking global information, such as connectivity patterns.
This oversight can result in suboptimal selection because global information is crucial for ensuring that the selected samples well represent the structural properties of the graph.
To address this issue, we employ structural entropy to quantify global information and losslessly decompose it from the whole graph to individual nodes using the Shapley value.
Based on the decomposition, we present S tructural- E ntropy-based sample S election ( SES ), a method that integrates both global and local information to select informative and representative samples.
SES begins by constructing a k 𝑘 k italic_k NN-graph among samples based on their similarities.
It then measures sample importance by combining structural entropy (global metric) with training difficulty (local metric).
Finally, SES applies importance-biased blue noise sampling to select a set of diverse and representative samples.
Comprehensive experiments on three learning scenarios — supervised learning, active learning, and continual learning — clearly demonstrate the effectiveness of our method.

## 1 Introduction

Data budgets that limit sample sizes are pervasive in machine learning applications.
For example, researchers and practitioners often face limited annotation and computational resources, necessitating the use of fewer but more informative samples to enhance efficiency.
Similarly, in continual learning scenarios (Hou et al., ), the memory constraint requires fewer but more representative samples from previous tasks to effectively retain knowledge.
Consequently, effective sample selection becomes crucial to improving efficiency and effectiveness in machine learning.
It aims to select informative and representative samples from large datasets to accelerate training and enhance the training performance.
During selection, samples can be modeled as a sample graph, where nodes are samples and edges represent their similarities.
Existing sample selection methods primarily focus on local information, such as training difficulty and node degree (Maharana et al., ).
Although these methods demonstrate promising performance on many datasets, they overlook the global information inherent in the graph structure.
This global information, such as connectivity patterns, captures the structural properties of the whole graph (Leskovec & Faloutsos, ) and has been shown to be effective in improving the representativeness of selected samples (Zhang et al., ; Yuan et al., ; Zhao et al., ).
Therefore, we aim to incorporate global information into the sample selection process to improve the quality of the selected samples.

The key to incorporating global information is to identify which specific metric(s) can accurately capture the global structure of the sample graph.
Li & Pan () propose structural entropy to evaluate the amount of information required to describe a given graph structure.
The main feature of this metric is that it is robust and sensitive.
First, it remains stable against minor changes like the addition or removal of a few edges.
This ensures that the structural entropy reliably reflects the global structure of the graph despite potential noise.
Second, it is sensitive to topological changes, especially those affecting connectivity patterns.
This is essential for capturing the global structure in response to even small topological changes.
These two properties make structural entropy an effective metric for quantifying the global structure and therefore valuable in sample selection.
However, existing methods only provide a single value for the whole graph.
This presents a challenge in decomposing this metric to the level of individual nodes, limiting its utility for fine-grained, node-level selection.

To address this challenge, we use the Shapley value (Shapley, ), a method that fairly decomposes a metric among contributors based on their individual contributions.
Specifically, it is calculated by evaluating a node’s marginal contribution to structural entropy when adding this node to each subgraph of the sample graph.
This decomposition process is highly time-consuming as it requires the enumeration of all possible subgraphs.
To accelerate this, we reformulate the Shapley value for structural entropy, enabling linear-time calculation with respect to the number of edges.
Based on this reformulation, we develop a node-level structural entropy metric that effectively measures the importance of nodes in preserving the global structure.
Building on the decomposition, we present a Structural-Entropy-based sample Selection (SES) method that integrates both global and local metrics to select informative and representative samples.
This method begins by constructing a $k$NN-graph among samples to describe their similarity relationships.
Then, it measures sample importance by combining node-level structural entropy (global metric) with training difficulty (local metric).
Finally, the importance-biased blue noise sampling method is employed to iteratively select a set of diverse and representative samples.

We validate the effectiveness of our method through comprehensive experiments on three important learning scenarios: supervised learning, active learning, and continual learning.
The evaluation covers many tasks, including image classification, text classification, object detection, and visual question answering.
The results clearly show that our method consistently improves the state-of-the-art methods across all scenarios and tasks.
This indicates that our method of integrating global and local information outperforms existing methods in selecting more informative and representative samples.

The main contributions of this work are threefold:

- •
Node-level structural entropy that quantifies the importance of nodes in preserving the global structure.
- •
A structural-entropy-based sample selection method that integrates both global and local metrics to select informative and representative samples(^1^11The implementation is available at [https://anonymous.4open.science/r/SE-based$_$sample$_$selection-575B/](https://anonymous.4open.science/r/SE-based_sample_selection-575B/).).
- •
Experiments in supervised learning, active learning, and continual learning that demonstrate the effectiveness of our method.

## 2 Related work

Existing sample selection methods primarily utilize local information.
They can be classified into two categories based on the information utilized: attribute-based methods and connection-based methods.

Attribute-based methods rely on the attributes of individual samples.
A commonly used attribute is the training difficulty,
which is typically assessed from two perspectives: confidence and error.
Metrics that measure model confidence include the entropy of the prediction vector (Coleman et al., ) and the variance of the predicted probabilities across training epochs (Swayamdipta et al., ).
Metrics that measure model error include EL2N (Paul et al., ), which calculates the $L_{2}$ norm of the error vector, and the Forgetting score (Toneva et al., ), which tracks the frequency of misclassifications after initial correct classifications.
AUM (Pleiss et al., ) combines both perspectives by measuring the confidence for correct classifications and the error for misclassifications.
Based on these metrics, several sample selection methods have been developed.
One simple yet effective method is selecting the most difficult samples, as they have a larger impact on model performance (Paul et al., ).
However, this method overlooks easy samples, which are crucial for model training when data budgets are limited (Sorscher et al., ).
To address this issue,
CCS (Zheng et al., ) divides the dataset into strata based on training difficulty and performs random sampling within each stratum.
InfoBatch (Qin et al., ) retains some easy samples and enhances their influence by upscaling their gradient.
Another line of work uses the gradient as the attribute and aims to match the average gradient of the selected samples with that of all samples (Mirzasoleiman et al., ; Killamsetty et al., ).
However, these gradients depend on the model’s current state during training, limiting the applicability of the selected samples to other models.

Connection-based methods utilize local connections within the sample graph to optimize sample diversity and coverage.
GraphCut (Iyer et al., ) selects samples with weak connections among them to promote diversity while maintaining strong connections to unselected samples for better coverage.
Moderate coreset (Xia et al., ) selects samples based on their distances from the class centers.
To enhance the generalizability across different scenarios, samples near the median distance are selected.
$\mathbb{D}^{2}$ Pruning (Maharana et al., ) aims to select difficult and diverse samples.
It employs forward message passing to integrate training difficulty and node degree, followed by backward message passing to ensure diversity.

While these methods demonstrate promising performance on many datasets, they often overlook the global information, which is crucial for increasing the representativeness of selected samples (Yuan et al., ).
Overlooking this global information can lead to suboptimal learning performance.
To address this gap, we propose a structural-entropy-based sample selection method that integrates both global and local metrics to select informative and representative samples.
The experimental results presented in Sec. LABEL:sub@sec:exp show that our method achieves consistent improvement over existing methods.

## 3 Background: Structural Entropy of Graph

Figure: Figure 1: The structural entropy calculation for an undirected, weighted graph.
Refer to caption: x1.png

Structural entropy evaluates how the nodes and edges in a graph are hierarchically organized to form communities at different levels (Li & Pan, ).
Thus, it is effective in globally quantifying the community structure of the graph regarding its overall connectivity patterns.
The calculation of structural entropy is based on an encoding tree that represents the graph’s hierarchical community structure.
In this tree, each node represents a community, and each leaf node corresponds to a graph node that forms a single-node community.
With this encoding tree, the entropy is aggregated across communities of different levels, which provides insights into the hierarchical community structure of the graph.
Fig. LABEL:sub@fig:codingtree shows an undirected, weighted graph $G$ and its encoding tree $\mathcal{T}$.
The entropy is calculated for each non-root node $\alpha$, which considers both intra-community and inter-community connections to reflect the connectivity patterns of its community in the graph.
Lower entropy indicates denser intra-community connections and sparser inter-community connections.
The intra-community connection, $vol(\alpha)$, is quantified by the total weighted degrees of nodes,
while the inter-community connection, $g(\alpha)$, is quantified by the total weight of the edges with exactly one endpoint in the community (outer edges).
Given an encoding tree $\mathcal{T}$, the structural entropy of $G$ is the aggregation of the entropy values from all its non-root nodes:

$$ $\mathcal{H}(G,\mathcal{T})=-\sum_{\alpha\in\mathcal{T}}\frac{g(\alpha)}{vol(V) }\log{\frac{vol(\alpha)}{vol(\alpha^{-})}},$ (1) $$

where $\alpha$ is a non-root node, $\alpha^{-}$ is its parent node, $g(\alpha)$ is the total weight of its outer edges, and $vol(V)$, $vol(\alpha)$, $vol(\alpha^{-})$ represent the total weighted degrees of the nodes in $V$, $\alpha$, and $\alpha^{-}$.

In real-world applications, the encoding tree $\mathcal{T}$ may be unknown.
To best capture the hierarchical community structure in such cases, the encoding tree $\mathcal{T}$ is constructed by minimizing the structural entropy.
Obtaining an exact solution for the minimization is challenging, so a greedy strategy similar to the Huffman tree construction has been developed (Zhu et al., ).

## 4 Structural-Entropy-Based Sample Selection

Our sample selection method integrates global and local metrics to select informative and representative samples.
Given a large set of samples, an undirected, weighted sample graph $G$ is initially constructed to model their similarity relationships.
Each sample, represented by its embedding extracted by a deep neural network, corresponds to a node in the graph.
To avoid excessive edge connections, each sample is connected to its $k$ nearest neighboring samples.
The edge weight between any two samples, $u$ and $v$, is their cosine similarity normalized to $[0,1]$.
Based on this graph, we first propose a node-level structural entropy metric to globally measure the importance of each sample.
Then, it is combined with a local metric, training difficulty, to assign an importance score to each sample.
Using this score, we develop an importance-biased blue noise sampling method to select a set of informative and representative samples.

### 4.1 Node-Level Structural Entropy

The core of our scoring method is to define the metric at the node level.
While local metrics are well studied, global metrics have received little attention.
An ideal global metric for fine-grained, node-level selection should measure the connectivity patterns of a graph at the individual node level.
Previous research shows that the graph-level structural entropy effectively quantifies the global connectivity patterns (Li & Pan, ), making it a valuable metric for sample selection.
However, it only provides a single value for the whole graph, thus failing to offer detailed insights at the node level.
Consequently, the key is to decompose the graph-level structural entropy to the node level.

Chen & Teng () have shown that Shapley value (Shapley, ) is an effective method to decompose a value from the graph level to the node level.
The key feature of this method is its lossless and fair decomposition of the value, ensuring that the aggregate node-level value equals the graph-level value.
Inspired by this, we employ the Shapley value to derive the node-level structural entropy.
Specifically, the Shapley value of a node $u$ reflects the average increase in structural entropy when it is added to all possible subgraphs of $G$.
As a result, this value captures the node’s contribution to the global connectivity patterns.

To derive the Shapley value for each node, we first calculate the structural entropy for each possible subgraph of $G$.
Then, we calculate the node’s contribution to these subgraphs.
Formally, let $V_{S}$ denote a subset of the node set $V$, the Shapley value of node $u$ is:

$$ $\phi(u)=\frac{1}{|V|}\sum_{V_{s}\subseteq V\backslash\{u\}}\binom{|V|-1}{|V_{S }|}^{-1}\Big{(}\mathcal{H}(G[V_{S}\cup\{u\}],\mathcal{T})-\mathcal{H}(G[V_{S}] ,\mathcal{T})\Big{)},$ (2) $$

where $G[V_{S}]$ is the subgraph of $G$ that consists of nodes in $V_{S}$ and the edges between them, and $\binom{|V|-1}{|V_{S}|}$ is the binomial coefficient.

Directly calculating Eq. (LABEL:sub@equ:Shapley) requires an enumeration of all possible subgraphs of $G$, which becomes intractable for a graph with a large number of nodes.
To address this, we reformulate the Shapley value by considering the contribution of edges.

###### Proposition 1 .

Let $G\mkern-2.0mu=\mkern-2.0mu(V,E,W)$ be an undirected, weighted graph. The Shapley value of node $u$ is

$$ $\phi(u)=\frac{1}{vol(V)}\Bigg{(}\sum_{\langle u,v\rangle\in E}w_{u,v}\log vol( \alpha_{u\vee v})-d(u)\log d(u)\Bigg{)},$ (3) $$

where $w_{u,v}$ is the weight of edge $\langle u,v\rangle$, $\alpha_{u\vee v}$ is the least common ancestor of node $u$ and $v$ in the encoding tree $\mathcal{T}$, and $d(u)$ is the weighted degree of node $u$.

###### Proof.

The proof of this proposition is provided in Appendix LABEL:sub@appendix:proof.
∎

Proposition LABEL:sub@prop:se shows that the Shapley value can be calculated in linear time with respect to the number of edges.
Thus, this reformulation enables an efficient and exact calculation.
In particular, the calculation consists of two terms.
The first decomposes the structural entropy from the encoding tree to the node, and the second reflects local connectivity through node degree.
Given our emphasis on developing a global metric, we only use the first term to define the node-level structural entropy ($S_{e}$):

$$ $S_{e}(u)=\frac{1}{vol(V)}\sum_{\langle u,v\rangle\in E}w_{u,v}\log vol(\alpha_ {u\vee v}).$ (4) $$

Figure: Figure 2: Edges connecting: (a) nodes $u$ and $v$ across different communities; (b) nodes $u$ and $v^{\prime}$ within the same community.

A higher $vol(\alpha_{u\vee v})$ indicates that the edge $\langle u,v\rangle$ connects nodes that are more distantly located in $\mathcal{T}$.
For example, in Fig. LABEL:sub@fig:lca(a), the edge $\langle u,v\rangle$ connects nodes across different communities.
In contrast, in Fig. LABEL:sub@fig:lca(b), the edge $\langle u,v^{\prime}\rangle$ connects nodes within the same community, resulting in a lower $vol(\alpha_{u\vee v^{\prime}})$ compared to $vol(\alpha_{u\vee v})$.
Thus, $vol(\alpha_{u\vee v})$ effectively quantifies the extent to which an edge bridges different communities.
Given that the node-level structural entropy is the weighted sum of $vol(\alpha_{u\vee v})$, nodes with high structural entropy serve as boundaries between communities.
Selecting these nodes is crucial for maintaining the overall structure of the graph.

###### Proposition 1 .

###### Proof.

### 4.2 Importance-Biased Blue Noise Sampling

To select a set of high-quality samples, the developed global metric, node-level structural entropy, needs to be combined with an appropriate local metric.
Previous research has shown that training difficulty ($S_{t}$) is an effective local metric in quantifying the sample’s impact on model performance (Paul et al., ; Sorscher et al., ).
Based on this, we employ it as the local metric.
Accordingly, the overall importance score ($S$) of a sample is a combination of node-level structural entropy and training difficulty:

$$ $S(u)=S_{e}(u)\cdot S_{t}(u).$ (5) $$

Given the importance scores, a straightforward solution is to select the samples with the highest scores.
However, this significantly reduces the diversity of the selected samples, as the important samples tend to cluster in several narrow regions (Zheng et al., ).
An alternative is the message passing mechanism employed by $\mathbb{D}^{2}$ Pruning:
once a sample is selected, this method sends weighted messages to decrease the importance scores of its neighbors in the graph.
However, the message weights are sensitive to a hyperparameter and can lead to suboptimal results if not carefully tuned.
Previous research has shown that blue noise sampling achieves a good balance between randomness and uniformity by excluding overly similar samples (Xiang et al., ; Liu et al., ).
This method increases sampling in low-density regions, which enhances the diversity of the selected samples.
Consequently, we develop an importance-biased blue noise sampling method to select a set of informative and representative samples.

Our sampling process contains two steps:
1) identifying the candidate sample with the highest importance score,
2) rejecting the sample if its similarity with any selected neighboring samples exceeds a threshold $\theta$; otherwise, accepting it as a selected sample.
These two steps are iteratively performed until no more samples can be selected.
To determine the threshold $\theta$ for a given sampling rate, we perform a binary search on $\theta$.

## 5 Experiments

In this section, we first demonstrate the effectiveness of our method in three learning scenarios: supervised learning, active learning, and continual learning.
We then conduct ablation studies to provide insights into our method.
Finally, we conduct a qualitative analysis of the selection results.

### 5.1 Supervised Learning

In supervised learning tasks, including image classification, text classification, object detection, and visual question answering, we aim to reduce computational costs by selecting a subset of informative and representative samples for training.

#### 5.1.1 Experimental Setup

Datasets and models.
For image classification, we use the widely used datasets, CIFAR10, CIFAR100 (Krizhevsky, ), and ImageNet-1K (Deng et al., ).
Following Maharana et al. (), ResNet-18 (He et al., ) is used for CIFAR10 and CIFAR100, while ResNet-34 (He et al., ) is used for ImageNet-1K.
The models are trained from scratch on the selected subsets of the training set, and we report the model accuracy.

For text classification, we use the ANLI dataset (Nie et al., ), which focuses on natural language inference, and the IMDB Review dataset (Maas et al., ), which focuses on sentiment analysis.
Following Maharana et al. (), we fine-tune the RoBERTa model (Liu et al., ) and report the accuracy on the test set for both datasets.

For object detection, we use the PASCAL VOC dataset (Everingham et al., ), which contains bounding box annotations of objects and animals.
Following Choi et al. (), we train SSD (Liu et al., ) with VGG-16 (Simonyan & Zisserman, ) backbone from scratch and report the mAP on the test set.

For visual question answering, we use the CC SBU Align dataset (Zhu et al., ), which contains high-quality, aligned image-text pairs.
Following Wei et al. (), we fine-tune MiniGPT-4 (Zhu et al., ) on this dataset, and report the average accuracy of the model on five datasets: OKVQA (Schwenk et al., ), IconVQA (Lu et al., ), DocVQA (Mathew et al., ), GQA (Hudson & Manning, ), and ScienceQA (Saikh et al., ).

Please refer to Appendix LABEL:sub@appendix:exp_setting for more details on the dataset statistics and training hyperparameters.

Baselines. We compare our method with the state-of-the-art sample selection methods, which are either applicable to all tasks or designed for a specific task.
Baselines that are applicable to all tasks include:
1) Randomselection of samples,
2) Moderatecoreset (Xia et al., ),
3) CCS(Zheng et al., ),
4) $\mathbb{D}^{2}$Pruning(Maharana et al., ), and
5) GraphCut(Iyer et al., ).
For image classification and text classification, the task-specific baselines include selecting the most difficult samples based on:
1) Entropy(Coleman et al., ),
2) Forgettingscore (Toneva et al., ),
3) EL2N(Paul et al., ),
4) AUM(Pleiss et al., ), and
5) Variance(Swayamdipta et al., ).
For object detection, we include selection based on the AL-MDN uncertainty (Choi et al., ), which captures the detector’s overall uncertainty for an image.
For visual question answering, we include selection based on the Instruction score (Wei et al., ), which evaluates an image-text pair based on image-text matching degree and text length.

Implementation.
For all tasks, we extract image embeddings using CLIP (Radford et al., ) and text embeddings using Sentence-BERT (Reimers & Gurevych, ) due to their demonstrated performance.
For visual question answering, we concatenate the image and text embeddings for each sample.
To measure training difficulty, we use AUM for image classification, Variance for text classification, AL-MDN uncertainty for object detection, and Instruction score for visual question answering.
We ablate the different training difficulty metrics in Sec. LABEL:sub@sec:abl and observe that there is no significant performance difference among them.
We also perform a grid search on the hyperparameters, such as $k$ in the $k$NN-graph construction (see Appendix LABEL:sub@appendix:hyper_setting for details).

#### 5.1.2 Results

To cover a wide range of sampling rates,
we select subsets that contain $1\%$, $2\%$, $5\%$, $10\%$, $20\%$, $50\%$, and $70\%$ of the entire training set.
All the results are averaged over 5 random seeds.
Table LABEL:sub@tab:dataset_sum_main shows the results on four datasets that cover all the four tasks.
The full results are provided in Appendix LABEL:sub@appendix:eva_result.

Baselines that select the most difficult samples, such as AUM and Forgetting, perform well in high-rate settings.
However, these methods fall behind in low-rate settings.
This is due to their limited coverage of easy samples, which are crucial for model training when fewer samples are selected (Sorscher et al., ).
Methods that prioritize sample coverage, such as CCS and $\mathbb{D}^{2}$ Pruning, address this issue and perform well in low-rate settings.
However, in high-rate settings, they cannot accurately determine the most important samples that preserve global structure.
This results in a lack of representativeness in the selected samples and suboptimal performance.
In contrast, our method integrates both global and local metrics to better identify important samples and employs importance-biased blue noise sampling to ensure representativeness.
Therefore, our method consistently performs better than baselines across all sampling rates and datasets.

In text classification and visual question answering, we observe that decreasing the sampling rate does not significantly affect performance.
This is because we are fine-tuning pretrained models, which provide sufficient knowledge for these tasks.
By providing high-quality samples, our method significantly accelerates fine-tuning with negligible performance loss.
For example, as shown in Table LABEL:sub@tab:okvqa, we achieve a $10$x speedup by using only $10\%$ of the dataset to fine-tune MiniGPT-4, with only a $0.3\%$ drop in accuracy compared to using the entire dataset.

**Table 1: Results for supervised learning on: (a) ImageNet-1K; (b) ANLI; (c) PASCAL VOC; (d) CC SBU Align. The best one is bold, and the runner-up is underlined.**
| Dataset | ImageNet-1K (100%:73.63) |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Sampling rate | 70% | 50% | 20% | 10% | 5% | 2% | 1% |
| Random | 71.63 | 69.26 | 58.90 | 47.10 | 34.04 | 16.56 | 5.50 |
| Moderate | 71.33 | 68.72 | 55.23 | 40.97 | 25.75 | 11.33 | 4.52 |
| CCS | 70.74 | 69.23 | 60.04 | 50.41 | 36.92 | 19.92 | 9.43 |
| $\mathbb{D}^{2}$ Pruning | 71.29 | 70.32 | 58.91 | 50.81 | 37.12 | 18.97 | 11.23 |
| GraphCut | 68.91 | 68.72 | 55.28 | 44.79 | 33.54 | 20.07 | 11.49 |
| Entropy | 70.93 | 69.21 | 54.76 | 38.46 | 22.78 | 7.01 | 1.95 |
| Forgetting | 70.57 | 70.46 | 60.77 | 48.73 | 33.86 | 15.13 | 5.66 |
| EL2N | 71.68 | 65.98 | 31.90 | 12.57 | 6.50 | 3.25 | 1.90 |
| AUM | 69.94 | 65.36 | 21.91 | 10.50 | 6.42 | 3.58 | 2.24 |
| Variance | 70.12 | 66.09 | 35.15 | 13.85 | 7.13 | 4.72 | 1.81 |
| SES (Ours) | 72.80 | 71.05 | 63.24 | 53.59 | 41.88 | 25.59 | 13.43 |

### 5.2 Active Learning

Active learning (Settles, ) aims to reduce annotation effort by selecting a set of informative and representative samples from an unlabeled pool.
These samples are then labeled to train models.

#### 5.2.1 Experimental Setup

Datasets and models.
To evaluate the effectiveness of the selection methods in an active learning task, we perform image classification on ImageNet-1K.
To simulate an unlabeled pool, we remove the labels from all samples during selection.
After selection, we use the ground-truth labels to simulate human annotations.
We train ResNet-34 from scratch on these labeled images and report the accuracy on the ImageNet-1K validation set.

Baselines.
We include the baselines from Sec. LABEL:sub@subsec:supervised that are applicable to unlabeled datasets:
1) Random,
2) CCS,
3) $\mathbb{D}^{2}$Pruning, and
4) GraphCut.
Additionally, we include Prototypicality (Sorscher et al., ) designed for unlabeled datasets.
This method selects the most difficult samples based on the prototypicality score, which is defined as the distance between samples and their corresponding $k$-means cluster center.
Difficult samples are those far from the center, as they tend to be more ambiguous than the samples closer to the center.

Implementation.
In the active learning scenario, using a pretrained supervised model like CLIP for feature extraction is not suitable, because the domain of the unlabeled data may not be covered by its pretraining data.
Therefore, we extract the image embeddings with a self-supervised model, SwAV (Caron et al., ).
In the baselines and our method, the prototypicality score is utilized to measure training difficulty.

#### 5.2.2 Results

We select unlabeled samples with rates of $1\%$, $2\%$, $5\%$, $10\%$, $20\%$, $50\%$, and $70\%$ and report the results averaged over 5 random seeds in Table LABEL:sub@tab:active.
In low-rate settings, other baselines perform worse than random selection due to the absence of labels, indicating their reliance on labeled data to achieve optimal performance.
In contrast, our method consistently performs better than random selection and other baseline methods.
This is because structural entropy compensates for missing labels by capturing community structure in datasets.

### 5.3 Continual Learning

Continual learning (Kirkpatrick et al., ) aims to alleviate the catastrophic forgetting of previously learned tasks when learning new tasks over time.
We focus on the replay-based method (Hou et al., ), which selects a small set of informative and representative samples from previous tasks and replays them during the training of new tasks.

**Table 2: Results for active learning. The best one is bold, and the runner-up is underlined.**
| Dataset | ImageNet-1K (100%:73.63) |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Sampling rate | 70% | 50% | 20% | 10% | 5% | 2% | 1% |
| Random | 71.12 | 69.43 | 58.77 | 47.36 | 33.41 | 16.41 | 5.41 |
| Moderate | 71.48 | 68.68 | 56.35 | 42.29 | 26.77 | 11.37 | 4.22 |
| CCS | 71.46 | 69.50 | 58.85 | 45.06 | 28.02 | 9.03 | 2.33 |
| GraphCut | 71.50 | 69.16 | 56.08 | 40.99 | 24.30 | 7.90 | 2.46 |
| $\mathbb{D}^{2}$ Pruning | 71.62 | 69.02 | 59.65 | 45.97 | 28.08 | 14.24 | 4.79 |
| Prototypicality | 70.12 | 66.00 | 49.20 | 35.27 | 24.14 | 13.88 | 4.95 |
| SES (Ours) | 72.11 | 70.15 | 60.22 | 48.10 | 34.82 | 17.97 | 6.69 |

#### 5.3.1 Experimental Setup

Datasets and models.
We use the datasets commonly used in continual learning, including Permuted MNIST, Split MNIST, Split CIFAR10, Split CIFAR100, and Split Tiny-ImageNet.
Permuted MNIST splits MNIST (LeCun et al., ) into $10$ segments, where a fixed permutation of the pixel order is applied to all images in each segment to simulate different distributions.
Thus, it contains $10$ classification tasks with samples from different distributions.
The other four datasets split the image classes in MNIST, CIFAR10, CIFAR100, and Tiny-ImageNet (Le & Yang, ) into $5$, $5$, $20$, and $20$ segments, respectively, and each segment corresponds to a different classification task.
In alignment with prior studies (Borsos et al., ; Hao et al., ), we use increasingly complex models as dataset complexity grows: a two-layer MLP for Permuted MNIST, a four-layer CNN for Split MNIST, ResNet-18 for Split CIFAR10, and ResNet-18 with multi-head output (Zenke et al., ) for Split CIFAR100 and Split Tiny-ImageNet.
The models are trained sequentially on each task while maintaining a fixed-size replay memory that contains an equal number of samples for each previous task.
During training, samples from both the replay memory and the current task are used, with the replay samples weighted by a hyperparameter that controls their influence on the current task.
After completing each task, a subset of samples is selected from the current task to replace a portion of the replay memory.
We report the average accuracy on all tasks.

Baselines.
We include all baselines from Sec. LABEL:sub@subsec:supervised to select samples that update the replay memory.
Additionally, we include three state-of-the-art selection methods designed for continual learning:
1) iCaRL(Rebuffi et al., )that selects samples whose average embedding closely approximates the average embedding of all samples,
2) Greedy Coreset(Borsos et al., )that formulates the selection as a bilevel optimization problem and greedily selects samples such that the model trained on them minimizes the loss across the entire dataset, and
3) BCSR(Hao et al., )that formulates the selection as a bilevel optimization problem on the probability simplex over samples and introduces a regularizer to control the number of selected samples.

Implementation.
Consistent with the implementation in Sec. LABEL:sub@subsec:supervised, we extract the image embeddings with CLIP and measure training difficulty with AUM.
For all baselines and our method, we perform a grid search on the weight of replay samples during training to determine its optimal value (see Appendix LABEL:sub@appendix:exp_setting for details).

#### 5.3.2 Results

Following Borsos et al. (), we test replay memory sizes of $100$ and $200$ and report the results averaged over 5 random seeds in Table LABEL:sub@tab:continual.
Our method consistently achieves better performance than baselines across all memory sizes and datasets.
This is because the combination of node-level structural entropy and training difficulty captures both the global structure of samples and the model training dynamics in retaining knowledge.

**Table 3: Results for continual learning. The best one is bold, and the runner-up is underlined.**
| Dataset | Permuted<br>MNIST | Split<br>MNIST | Split<br>CIFAR10 | Split<br>CIFAR100 | Split<br>Tiny-ImageNet |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Memory size | 100 | 200 | 100 | 200 | 100 | 200 | 100 | 200 | 100 | 200 |
| Random | 77.43 | 79.69 | 95.79 | 97.16 | 62.34 | 63.69 | 51.29 | 54.22 | 18.52 | 19.22 |
| Moderate | 78.29 | 79.44 | 95.34 | 97.05 | 61.51 | 63.01 | 51.91 | 53.45 | 18.63 | 19.47 |
| CCS | 75.48 | 76.53 | 89.50 | 94.92 | 60.56 | 61.04 | 48.70 | 51.26 | 18.30 | 18.90 |
| $\mathbb{D}^{2}$ Pruning | 78.25 | 79.94 | 96.79 | 97.69 | 64.54 | 66.08 | 51.86 | 54.50 | 19.08 | 19.50 |
| GraphCut | 76.98 | 78.61 | 91.34 | 94.25 | 61.02 | 61.66 | 53.35 | 54.66 | 19.76 | 20.53 |
| Entropy | 75.54 | 78.18 | 91.54 | 96.16 | 61.53 | 62.72 | 47.97 | 51.51 | 17.99 | 18.62 |
| Forgetting | 75.30 | 77.47 | 92.13 | 96.37 | 59.56 | 61.38 | 53.06 | 54.68 | 19.55 | 19.56 |
| EL2N | 75.57 | 77.48 | 88.54 | 94.87 | 57.79 | 58.34 | 46.47 | 48.11 | 17.95 | 17.98 |
| AUM | 75.54 | 77.47 | 90.38 | 95.79 | 58.32 | 58.06 | 46.14 | 47.20 | 18.24 | 17.89 |
| Variance | 75.67 | 77.42 | 91.90 | 94.96 | 58.69 | 57.77 | 52.83 | 54.00 | 19.32 | 19.50 |
| iCaRL | 78.94 | 80.65 | 89.50 | 97.59 | 62.33 | 64.08 | 54.62 | 56.11 | 19.58 | 19.85 |
| Greedy Coreset | 78.71 | 80.13 | 96.07 | 97.76 | 63.18 | 62.98 | 56.17 | 57.72 | 19.24 | 19.98 |
| BCSR | 77.74 | 79.51 | 94.77 | 96.98 | 63.23 | 64.59 | 50.21 | 51.49 | 18.75 | 18.74 |
| SES (Ours) | 79.92 | 81.18 | 96.94 | 98.28 | 68.26 | 69.32 | 57.60 | 59.69 | 20.80 | 21.20 |

**Table 4: Ablation of modules. The best one is bold, and the runner-up is underlined.**
| Module | Sampling rate | Avg. |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Scoring | Sampling | 70% | 50% | 20% | 10% | 5% | 2% | 1% |  |
| TD | HS | 94.85 | 93.90 | 70.88 | 60.68 | 47.36 | 38.30 | 32.41 | 62.63 |
| TD | MP | 94.86 | 94.28 | 87.88 | 77.68 | 65.30 | 49.69 | 41.41 | 73.01 |
| TD | BNS | 94.88 | 94.05 | 88.06 | 79.55 | 68.05 | 53.37 | 43.07 | 74.43 |
| SE+TD | HS | 94.92 | 94.39 | 82.03 | 70.42 | 57.63 | 40.64 | 33.68 | 67.67 |
| SE+TD | MP | 95.08 | 94.67 | 88.54 | 80.14 | 69.34 | 54.26 | 44.51 | 75.22 |
| SE+TD | BNS | 95.01 | 94.50 | 88.31 | 80.24 | 69.82 | 54.78 | 45.25 | 75.42 |

### 5.4 Ablation Study

We conduct ablation studies on supervised learning using CIFAR10 to evaluate the impact and behavior of each module in our method.

Effect of modules.
We ablate the two key modules in our method, node-level structural entropy (SE) and importance-biased blue noise sampling (BNS), by replacing them with alternatives.
Without SE, we score samples based solely on training difficulty (TD).
Without BNS, we either select samples with the highest scores (HS) or use the message passing (MP) method from $\mathbb{D}^{2}$ pruning.
The hyperparameter controlling message weights in MP is searched as in the original paper (Maharana et al., ).
Table LABEL:sub@tab:aba_module shows the results.
Using TD and HS yields the lowest performance.
Incorporating either SE, BNS, or MP largely improves performance, demonstrating their individual effectiveness.
Combining SE with either BNS or MP further improves the performance, indicating that SE complements both methods in selecting informative and representative samples.
Notably, BNS achieves comparable performance to MP without the need for tuning the additional hyperparameter, demonstrating its effectiveness.

Robustness to different training difficulty metrics.
We test the effect of using different training difficulty metrics, including Forgetting, EL2N, and AUM.
We also include the identity baseline, which assigns identical scores to all samples.
Table LABEL:sub@tab:aba_diff shows the results.
Using identical scores leads to inferior performance, indicating the importance of incorporating training difficulty.
Meanwhile, using AUM, Forgetting, and EL2N yields comparable performance, with average accuracies across rates differing by no more than $0.5\%$.
This demonstrates the robustness of our method to the choice of the training difficulty metric.

**Table 5: Ablation of training difficulty metrics. The best one is bold, and the runner-up is underlined.**
| Difficulty<br>metric | Sampling rate | Avg. |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 70% | 50% | 20% | 10% | 5% | 2% | 1% |  |  |
| Identity | 94.58 | 92.66 | 86.67 | 78.50 | 67.68 | 53.21 | 44.43 | 73.96 |
| Forgetting | 94.86 | 93.99 | 88.11 | 79.06 | 70.45 | 53.99 | 46.43 | 75.27 |
| EL2N | 94.61 | 93.74 | 88.45 | 79.93 | 69.52 | 54.01 | 45.15 | 75.06 |
| AUM | 95.01 | 94.50 | 88.31 | 80.24 | 69.82 | 54.78 | 45.25 | 75.42 |

Figure: Figure 3: Ablation of $k$ in the $k$NN-graph construction.
Refer to caption: x2.png

Effect of $k$ in the $k$NN-graph construction.
We test the effect of $k$ in the $k$NN-graph construction.
Fig. LABEL:sub@fig:diff_k shows the results when selecting $10\%$ of the samples from CIFAR10.
As $k$ increases, the performance first increases and then remains relatively stable within a narrow range.
This indicates that the first few nearest neighbors effectively capture the global structure of the samples, which aligns with prior research (Jaffe et al., ).
Based on the grid search results across datasets, we empirically determine $\log_{2}{n}$ to be an appropriate value for $k$, where $n$ is the number of samples.

### 5.5 Qualitative Analysis

We visualize the selection results of different methods when selecting $2\%$ of the samples from CIFAR10 by projecting them onto a two-dimensional plane using t-SNE (van der Maaten & Hinton, ).
Fig. LABEL:sub@fig:quality shows the results of AUM, $\mathbb{D}^{2}$ Pruning, and our method.
The full results are provided in Appendix LABEL:sub@appendix:quali.
Methods that select the most difficult samples, such as AUM, oversample near several class boundaries and undersample in several classes that are easier to classify (Fig. LABEL:sub@fig:quality(a)).
Methods that prioritize sample coverage, such as $\mathbb{D}^{2}$ Pruning, achieve a better sample coverage but still miss critical samples near class boundaries (Fig. LABEL:sub@fig:quality(b)).
This gap indicates that these methods may not effectively preserve the global structure of samples.
Our method well covers the data distribution, providing a set of informative and representative samples for model training (Fig. LABEL:sub@fig:quality(c)).

Figure: Figure 4: Visualizations of results when selecting $2\%$ of the samples from CIFAR10 using: (a) AUM; (b) $\mathbb{D}^{2}$ Pruning; (c) our structural-entropy-based sample selection method.
Refer to caption: x3.png

## 6 Conclusion

In this paper, we present a structural-entropy-based sample selection method for efficient and effective learning.
The key idea behind our method is to decompose graph-level structural entropy to a node-level global metric using the Shapley value.
This global metric is combined with a local metric, training difficulty, for selecting informative and representative samples.
The effectiveness of our method is validated by comprehensive experiments on three learning scenarios.
Although our method has proven effective, future work on the following aspects is still promising.
First, automating the hyperparameter selection based on data characteristics can reduce the computational costs of the grid search.
Second, improving the support for multimodal data could strengthen its performance across a wider range of tasks, such as infographics VQA (Mathew et al., ) and building foundation models (Yang et al., ).

## Appendix A Proof of Proposition LABEL:sub@prop:se

We first present two lemmas essential for the proof of Proposition LABEL:sub@prop:se.

Lemma 1. Let $G=(V,E,W)$ be an undirected, weighted graph and $\mathcal{T}$ be its encoding tree.
Then the structural entropy $\mathcal{H}(G,\mathcal{T})$ can be written as:

$$ $\mathcal{H}(G,\mathcal{T})=\frac{1}{vol(V)}\Bigg{(}2\sum_{\langle u,v\rangle \in E}w_{u,v}\log vol(u\lor v)-\sum_{u\in V}d(u)\log d(u)\Bigg{)},$ $$

where $w_{u,v}$ is the weight of edge $\langle u,v\rangle$, $u\lor v$ is the least common ancestor of node $u$ and $v$ in $\mathcal{T}$, and $d(u)$ is the weighted degree of node $u$.

Proof of Lemma 1.
According to Eq. (LABEL:sub@equ:SE_def), we can derive that:

$$ $\begin{split}\mathcal{H}(G,\mathcal{T})&=-\sum_{\alpha\in\mathcal{T}}\frac{g( \alpha)}{vol(V)}\log\frac{vol(\alpha)}{vol(\alpha^{-})}\\ &=-\frac{1}{vol(V)}\sum_{\alpha\in\mathcal{T}}g(\alpha)\log\frac{vol(\alpha)}{ vol(\alpha^{-})}\\ &=\frac{1}{vol(V)}\sum_{\alpha\in\mathcal{T}}(g(\alpha)\log vol(\alpha^{-})-g( \alpha)\log vol(\alpha)).\\ \end{split}$ (6) $$

For a node $\alpha$ with $k$ children, the contribution of each child $\beta_{i}$ to the summation is
$g(\beta_{i})\log vol(\alpha)-g(\beta_{i})\log vol(\beta_{i}).$
The term $g(\beta_{i})\log vol(\alpha)$ can be combined into $-g(\alpha)\log vol(\alpha)$ due to the shared $\log vol(\alpha)$ factor.
By combining the terms with shared $\log vol(\cdot)$ factors, Eq. (LABEL:sub@eq:se_reform) can be rewritten as:

$$ $\mathcal{H}(G,\mathcal{T})=\frac{1}{vol(V)}\Bigg{(}\sum_{\alpha\text{ is non- leaf}}\bigg{(}\Big{(}\sum_{\beta\in\text{children}(\alpha)}g(\beta)\Big{)}-g( \alpha)\bigg{)}\log vol(\alpha)-\sum_{\alpha\text{ is leaf}}g(\alpha)\log vol( \alpha))\Bigg{)}.$ (7) $$

Note that $\sum_{\beta\in\text{children}(\alpha)}g(\beta)-g(\alpha)$ represents the difference between the total weight of outer edges of $\alpha$’s children and the total weight of outer edges of $\alpha$.
This difference is precisely twice the total weights of edges between the communities represented by $\alpha$’s children.
Furthermore, each edge $\langle u,v\rangle$ in the graph contributes only to the node $\alpha=u\lor v$.
Therefore, we can transform the first term into a sum over edges in the graph, yielding:

$$ $\mathcal{H}(G,\mathcal{T})=\frac{1}{vol(V)}\Bigg{(}2\sum_{\langle u,v\rangle \in E}w_{u,v}\log vol(u\lor v)-\sum_{\alpha\text{ is leaf}}g(\alpha)\log vol( \alpha)\Bigg{)}.$ (8) $$

The set of leaf nodes in the encoding tree corresponds to the set of nodes in the graph.
Additionally, for a leaf node $\alpha$ and its correpsonding graph node $u$, we have $g(\alpha)=vol(\alpha)=d(u)$.
We can conclude that:

$$ $\mathcal{H}(G,\mathcal{T})=\frac{1}{vol(V)}\Bigg{(}2\sum_{\langle u,v\rangle \in E}w_{u,v}\log vol(u\lor v)-\sum_{u\in V}d(u)\log d(u)\Bigg{)},$ (9) $$

which proves the lemma.

Lemma 2 (Winter, ). Eq. (LABEL:sub@equ:Shapley) is equivalent to:

$$ $\phi(u)=\frac{1}{|V|!}\sum_{\pi\in\Pi}\Big{(}\mathcal{H}(G[V_{\pi,u}\cup\{u\}] ,\mathcal{T})-\mathcal{H}(G[V_{\pi,u}],\mathcal{T})\Big{)},$ (10) $$

where $\Pi$ is the set of all permutations of nodes in $V$, and $V_{\pi,u}$ denotes the set of nodes preceding $u$ in permutation $\pi$.

Based on the two lemmas, we develop a proof of Proposition LABEL:sub@prop:se.

Proof of Proposition LABEL:sub@prop:se.
For brevity, we denote the subgraph $G[V_{\pi,u}\cup\{u\}]$ by $G_{\pi,u}^{+}=(V_{\pi,u}^{+},E_{\pi,u}^{+},W)$ and $G[V_{\pi,u}]$ by $G_{\pi,u}=(V_{\pi,u},E_{\pi,u},W)$.
Lemma 1 gives:

$$ $\mathcal{H}(G_{\pi,u}^{+},\mathcal{T})=\frac{1}{vol(V)}(2\sum_{\langle x,y \rangle\in E_{\pi,u}^{+}}w_{x,y}\log vol(x\lor y)-\sum_{x\in V_{\pi,u}^{+}}d(x )\log d(x))$ (11) $$

and

$$ $\mathcal{H}(G_{\pi,u},\mathcal{T})=\frac{1}{vol(V)}(2\sum_{\langle x,y\rangle \in E_{\pi,u}}w_{x,y}\log vol(x\lor y)-\sum_{x\in V_{\pi,u}}d(x)\log d(x)).$ (12) $$

Then

$$ $\begin{split}&\mathcal{H}(G_{\pi,u}^{+},\mathcal{T})-\mathcal{H}(G_{\pi,u}, \mathcal{T})\\ &=\frac{1}{vol(V)}\Bigg{(}2(\sum_{\langle x,y\rangle\in E_{\pi,u}^{+}}w_{x,y} \log vol(x\lor y)-\sum_{\langle x,y\rangle\in E_{\pi,u}}w_{x,y}\log vol(x\lor y ))\\ &-(\sum_{x\in V_{\pi,u}^{+}}d(x)\log(x)-\sum_{x\in V_{\pi,u}}d(x)\log d(x)) \Bigg{)}.\end{split}$ (13) $$

Note that $V_{\pi,u}^{+}=V_{\pi,u}\cup\{u\}$ and $E_{\pi,u}^{+}=E_{\pi,u}\cup\{\langle u,v\rangle:v\in\mathcal{N}(u)\cap V_{\pi,
u}\}$, where $\mathcal{N}(u)$ is the set of neighbors of $u$ in $G$.
Therefore,

$$ $\mathcal{H}(G_{\pi,u}^{+},\mathcal{T})-\mathcal{H}(G_{\pi,u},\mathcal{T})= \frac{1}{vol(V)}\Bigg{(}2\sum_{v\in\mathcal{N}(u)\cap V_{\pi,u}}w_{u,v}\log vol (u\lor v)-d(u)\log d(u)\Bigg{)}.$ (14) $$

We can rewrite $\sum_{v\in\mathcal{N}(u)\cap V_{\pi,u}}\log vol(u\lor v)$ as $\sum_{v\in\mathcal{N}(u)}\mathbb{I}[v\in V_{\pi,u}]\log vol(u\lor v)$, where $\mathbb{I}$ is the indicator function.
Then, the Shapley value in Eq. (LABEL:sub@equ:Shapley_equiv) can be rewritten as:

$$ $\begin{split}\phi(u)&=\frac{1}{|V|!}\sum_{\pi\in\Pi}\Big{(}\mathcal{H}(G[V_{ \pi,u}\cup\{u\}],\mathcal{T})-\mathcal{H}(G[V_{\pi,u}],\mathcal{T})\Big{)}\\ &=\frac{1}{|V|!}\sum_{\pi\in\Pi}\Bigg{(}\frac{1}{vol(V)}\bigg{(}2\sum_{v\in \mathcal{N}(u)}\mathbb{I}[v\in V_{\pi,u}]w_{u,v}\log vol(u\lor v)-d(u)\log d(u )\bigg{)}\Bigg{)}\\ &=\frac{2}{vol(V)|V|!}\sum_{\pi\in\Pi}\sum_{v\in\mathcal{N}(u)}\mathbb{I}[v\in V _{\pi,u}]w_{u,v}\log vol(u\lor v)-\frac{1}{vol(V)}d(u)\log d(u)\\ &=\frac{2}{vol(V)|V|!}\sum_{v\in\mathcal{N}(u)}w_{u,v}\log vol(u\lor v)\sum_{ \pi\in\Pi}\mathbb{I}[v\in V_{\pi,u}]-\frac{1}{vol(V)}d(u)\log d(u).\end{split}$ (15) $$

Note that $\sum_{\pi\in\Pi}\mathbb{I}[v\in V_{\pi,u}]$ is $\frac{|V|!}{2}$ since there are $\frac{|V|!}{2}$ permutations where $v$ precedes $u$. Thus, we have:

$$ $\begin{split}\phi(u)&=\frac{1}{vol(V)}\sum_{v\in\mathcal{N}(u)}w_{u,v}\log vol (u\lor v)-\frac{1}{vol(V)}d(u)\log d(u)\\ &=\frac{1}{vol(V)}\Bigg{(}\sum_{v\in\mathcal{N}(u)}w_{u,v}\log vol(\alpha_{u \lor v})-d(u)\log d(u)\Bigg{)}\\ &=\frac{1}{vol(V)}\Bigg{(}\sum_{\langle u,v\rangle\in E}w_{u,v}\log vol(\alpha _{u\vee v})-d(u)\log d(u)\Bigg{)},\end{split}$ (16) $$

which proves the proposition.

## Appendix B Dataset Statistics and Detailed Experimental Setting

### B.1 Supervised Learning

Image classification.
The CIFAR10 and CIFAR100 datasets each consist of $50,000$ images of 32×32 pixels for the training set, with an additional $10,000$ images for testing.
CIFAR10 includes 10 distinct classes, while CIFAR100 includes 100 classes.
The ImageNet-1K dataset includes $1,281,167$ images across $1,000$ real-world classes for training, along with $50,000$ images for validation.
Following common practice (Maharana et al., ), we trained ResNet-18 for 200 epochs on CIFAR10 and CIFAR100, and ResNet-34 for 60 epochs on ImageNet-1K.
The batch size is set to 64.
We use an SGD optimizer with an initial learning rate of 0.1, momentum of 0.9, and weight decay of 0.0002.
We use a cosine annealing learning rate scheduler with a minimum learning rate of 0.0001.

Text classification.
The ANLI dataset is a natural language inference dataset created through multiple rounds of iterative human-and-model-in-the-loop adversarial procedures.
We utilize the data from the final round, which consists of $100,459$ training samples and $1,200$ test samples.
Following previous work (Maharana et al., ), we fine-tune the RoBERTa model for $10,000$ iterations with a batch size of 16.
We use the SGD optimizer with an initial learning rate of 0.1, momentum of 0.9, and weight decay of 0.0005.
We use a cosine annealing scheduler with a minimum learning rate of 0.0001.

The IMDB Review dataset contains $25,000$ movie reviews each in the training and test splits, with each review labeled by sentiment (positive/negative).
Following previous work (Maharana et al., ), we randomly select $2,000$ samples from the original training set due to the excessive samples in it, and use the original test set for evaluation.
We fine-tune the RoBERTa model for $500$ iterations with a batch size of 16.
The optimizer and scheduler settings are the same as that for the ANLI dataset.

Object detection.
We train the model using the combined trainval sets of PASCAL VOC 2007 and 2012, which include $16,551$ images and $40,058$ objects across 20 categories.
The model is evaluated on the PASCAL VOC 2007 test set, which comprises $4,952$ images and $12,032$ objects.
We train SSD (Liu et al., ) with VGG-16 (Simonyan & Zisserman, ) backbone from scratch for 80 epochs with a batch size of 64.
We use an SGD optimizer with a learning rate of 0.001, momentum of 0.9, and weight decay of 0.0005.
The learning rate follows a linear warm-up strategy for the first 8 epochs and is then reduced by a factor of 10 at epochs 50 and 70.

Visual question answering.
The CC SBU Align dataset contains $3,439$ high-quality, aligned image-text pairs for the fine-tuning stage (stage 2) of Mini-GPT4 (Zhu et al., ).
The visual question answering datasets used for validation test the model’s abilities in various aspects, including logical reasoning, visual reasoning, knowledge retention, and abstract understanding.
We use the same setting as the second-stage fine-tuning for Mini-GPT4 (Zhu et al., ).
We fine-tune MiniGPT-4 for 400 iterations with a batch size of 12.
We use an SGD optimizer with an initial learning rate of 0.00003, momentum of 0.9, and weight decay of 0.05.
We use a cosine annealing scheduler with a minimum learning rate of 0.00001.

### B.2 Active learning

We use the same setting as training on ImageNet-1K in Sec. LABEL:sub@subsec:appendix_supervised.

### B.3 Continual learning

For continual learning, we follow Borsos et al. () for experiments on Permuted MNIST, Split MNIST, and Split CIFAR10, and follow Hao et al. () for experiments on Split CIFAR100 and Split Tiny-ImageNet.
We use increasingly complex models as dataset complexity grows: a two-layer MLP for Permuted MNIST, a four-layer CNN for Split MNIST, ResNet-18 for Split CIFAR10, and ResNet-18 with multi-head output (Zenke et al., ) for Split CIFAR100 and Split Tiny-ImageNet.
For each task, we first randomly select $\mathcal{M}$ samples from all available samples.
Then, we train the model on these samples for $E$ epochs with a batch size of $\mathcal{B}$.
During each training iteration, all replay samples are used with a weight of $\lambda$.
The initial learning rate is set to $lr_{t}$ for the first task and decays by a factor of $\eta$ for each task.
All hyperparameters, except $\lambda$, are fixed for all baselines and our method.
The value of $\lambda$ is determined through a grid search over $\{0.01,0.1,1,10,100,1000\}$.
Table LABEL:sub@tab:continual_param shows the fixed hyperparameters for different datasets.
Table LABEL:sub@tab:hyper_continual_baselines shows the optimal $\lambda$ for all baselines and our method.

**Table 6: Training hyperparameters for continual learning.**
| Hyperparameters | Permuted<br>MNIST | Split<br>MNIST | Split<br>CIFAR10 | Split<br>CIFAR100 | Split<br>Tiny-ImageNet |
| --- | --- | --- | --- | --- | --- |
| $\mathcal{M}$ | 1000 | 1000 | 1000 | 2500 | 5000 |
| Optimizer | Adam | Adam | Adam | SGD | SGD |
| $E$ | 400 | 400 | 400 | 1 | 1 |
| $\mathcal{B}$ | 256 | 256 | 256 | 10 | 20 |
| $lr_{t}$ | 0.0005 | 0.0005 | 0.0005 | 0.15 | 0.20 |
| $\eta$ | 1 | 1 | 1 | 0.875 | 0.875 |

**Table 7: Optimal replay sample weight $\lambda$ in continual learning.**
| Dataset | Permuted<br>MNIST | Split<br>MNIST | Split<br>CIFAR10 | Split<br>CIFAR100 | Split<br>Tiny-ImageNet |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Memory size | 100 | 200 | 100 | 200 | 100 | 200 | 100 | 200 | 100 | 200 |
| Random | 0.01 | 0.01 | 100 | 100 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 |
| Moderate | 0.01 | 0.01 | 100 | 100 | 0.1 | 0.1 | 0.01 | 0.01 | 0.01 | 0.01 |
| CCS | 0.01 | 0.01 | 1000 | 100 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 |
| $\mathbb{D}^{2}$ Pruning | 0.01 | 0.01 | 10 | 100 | 0.1 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 |
| GraphCut | 0.01 | 0.01 | 100 | 1 | 0.01 | 0.1 | 0.01 | 0.1 | 1 | 0.1 |
| Entropy | 0.01 | 0.01 | 1000 | 100 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 |
| Forgetting | 0.01 | 0.01 | 100 | 10 | 0.1 | 0.1 | 0.01 | 0.01 | 0.01 | 0.1 |
| EL2N | 0.01 | 0.01 | 100 | 100 | 0.01 | 0.1 | 0.01 | 0.01 | 0.01 | 0.01 |
| AUM | 0.01 | 0.01 | 100 | 100 | 10 | 1 | 0.01 | 0.01 | 0.01 | 0.01 |
| Variance | 0.01 | 0.01 | 1000 | 1000 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 |
| iCaRL | 0.01 | 0.1 | 100 | 100 | 1 | 1 | 0.01 | 0.01 | 0.1 | 0.1 |
| Greedy Coreset | 0.01 | 0.01 | 100 | 10 | 0.01 | 0.01 | 0.01 | 0.1 | 0.01 | 0.01 |
| BCSR | 0.01 | 0.01 | 100 | 10 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 |
| SES (Ours) | 0.01 | 0.1 | 100 | 100 | 1 | 1 | 0.01 | 0.1 | 0.01 | 0.1 |

·

## Appendix C Selection Hyperparameter Settings

### C.1 Selection Hyperparameters

We conducted a grid search to optimize three hyperparameters: the number of neighbors $k$ for constructing the $k$NN graph, the cutoff ratio $\beta$ to remove the most difficult samples, and the imbalance factor $\gamma$ to maintain the balance between different classes.

Selecting an appropriate value of $k$ is crucial as it can significantly affect the quality of the sample graph and thus affect the selection result.
If $k$ is too small, the graph becomes too sparse, making the selection sensitive to noise and outliers.
If $k$ is too large, the graph will be too dense and contain many edges connecting irrelevant neighbors, making it hard to identify the most important samples in the dataset.
Thus, the choice of $k$ must strike a balance to preserve meaningful structures without introducing noise or irrelevant information.

Inspired by  Zheng et al. (), we also search the hard cutoff ratio $\beta$ that removes $\beta$ of the most difficult samples because they are usually outliers and contain noisy samples in the dataset.
In addition, we also allow negative $\beta$ during the grid search, which indicates that we will remove $|\beta|$ of the easiest samples to focus on difficult samples, which has been adopted by  Sorscher et al. ().

Maintaining a balanced distribution of samples from different classes is also beneficial for model training.
A common strategy is to enforce strict class balance (Guo et al., ) by selecting an equal number of samples from each class.
However, this overlooks the difference between classes, where some may be more easily confused with others and require more samples to distinguish.
To address this, we introduce an imbalance factor $\gamma>1$, which allows for the selection of up to $n\dot{\gamma}$ samples per class, rather than a strict count of $n$.
This adjustment provides flexibility in addressing class-specific complexities.
In the active learning scenario, we treat the $k$-means clusters as the classes for balancing.

### C.2 Preliminary Experiments on k

As $k$ decides the sample graph and the range of possible $k$ is large, we conduct preliminary experiments on CIFAR10, CIFAR100, and ImageNet-1k to determine a candidate range where the structure of the sample graph is effectively preserved by the $k$NN-graph.

Spectral clustering is an effective method for revealing the underlying structural features of a graph.
Therefore, we use the spectral clustering results to evaluate the choice of $k$ in the preliminary experiments.
First, we perform spectral clustering on the $k$NN-graph.
Based on the spectral clustering results, we measure the structure preservation of the $k$NN-graph using both external and internal metrics.
The external metrics measure the consistency of the clustering results with the ground truth labels of samples.
We use the accuracy, the Rand Index, and the mutual information as the external metrics.
The internal metrics assess the quality of clustering by evaluating the compactness and separation of clusters.
We use the Silhouette Score and the Davis-Bouldin Index as the internal metrics.

Directly applying spectral clustering to large-scale datasets is unsuitable due to its high complexity of $O(n^{3})$, where $n$ is the number of samples in the dataset.
To address this, we use growing neural gas (Fritzke, ) to generate a reduced graph with fewer nodes.
The key feature of this method is the preservation of the topology of the $k$NN-graph.
Specifically, this method generates neurons representing the sample distribution of the $k$NN-graph.
Then, it integrates the edges in the $k$NN-graph into the neuron connections, resulting in a sparse, topology-preserving graph.
We apply spectral clustering to this reduced graph to accelerate the evaluation of the choice of $k$.

Figure: (a) CIFAR10
Refer to caption: x4.png

In the preliminary experiments, we test $k$ in $\{1,2,\dots,100\}$ on CIFAR10, CIFAR100, and ImageNet-1K.
Fig. LABEL:sub@fig:k_clustering presents the results.
As the value of $k$ increases, the performance metrics initially improve, then stabilize, and may eventually decline.
This suggests that the first few nearest neighbors effectively capture the structure of the original graph, while including too many neighbors may lead to underfitting due to edges connecting vastly different nodes.
We discover that the metrics begin to stabilize around $\log_{2}n$, where $n$ is the number of samples in the dataset.
Thus, we focus our grid search for $k$ values near $\log_{2}n$.

### C.3 Grid Search Results

For all experiments, we search $\beta$ in $\{-1,-0.95,\dots,-0.05,0,0.05,\dots,0.95,1\}$ and $\gamma$ in $\{1,1.05,\dots,1.5\}$.
For CIFAR10 and CIFAR100, we search $k$ in $\{10,11,\dots,30\}$.
For ImageNet-1K, we search it only in $\{20,25\}$ due to computational costs.
To save computational costs, we set $k$ to around $\log_{2}n$ for experiments on other datasets.
We evaluate every possible combination of the hyperparameters.
Table LABEL:sub@tab:hyper presents the optimal hyperparameters for supervised learning and active learning.
Table LABEL:sub@tab:continual_hyper presents the optimal hyperparameters for continual learning.

**Table 8: Optimal hyperparameters of our method in supervised learning and active learning. The three numbers in each tuple refer to the number of neighbors $k$, the cutoff ratio $\beta$, and the imbalance factor $\gamma$, respectively.**
| Sampling rate | CIFAR10 | CIFAR100 | ImageNet-1K | ANLI | IMDB Review | PASCAL VOC | VQA | ImageNet-1K<br>(active learning) |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 1% | (17,0.75,1.05) | (14,0.85,1.2) | (20,0.9,1.3) | (15,0.35,1.05) | (10,0.7,1.2) | (15,0.7,/) | (10,0.15,/) | (25,0.25,1.05) |
| 2% | (14,0.7,1.1) | (10,0.85,1.15) | (25,0.75,1.2) | (15,0.3,1.05) | (10,0.85,1.1) | (15,0.7,/) | (10,0.1,/) | (25,0.2,1.45) |
| 5% | (19,0.6,1.05) | (21,0.8,1.2) | (25,0.65,1.2) | (15,0.25,1.05) | (10,0.5,1.0) | (15,0.5,/) | (10,0.1,/) | (25,0.4,1.35) |
| 10% | (11,0.35,1.1) | (19,0.6,1.1) | (25,0.4,1.15) | (15,0.3,1.15) | (10,0.4,1.05) | (15,0.35,/) | (10,0.15,/) | (25,0.45,1.05) |
| 20% | (13,0.2,1.0) | (15,0.45,1.15) | (25,0.3,1.1) | (15,0.0,1.05) | (10,0.3,1.1) | (15,0.1,/) | (10,0.15,/) | (25,0.35,1.15) |
| 50% | (15,-0.15,1.0) | (15,0.15,1.0) | (20,0.05,1.05) | (15,0.0,1.1) | (10,0.05,1.05) | (15,0.15,/) | (10,0.1,/) | (25,0.0,1.1) |
| 70% | (24,0.0,1.0) | (18,0.1,1.0) | (20,0.0,1.0) | (15,0.0,1.2) | (10,0.05,1.0) | (15,0.05,/) | (10,0.0,/) | (25,0.0,1.15) |

**Table 9: Optimal hyperparameters of our method in continual learning. The three numbers in each tuple refer to the number of neighbors $k$, the cutoff ratio $\beta$, and the imbalance factor $\gamma$, respectively.**
| Memory size | Permuted<br>MNIST | Split<br>MNIST | Split<br>CIFAR10 | Split<br>CIFAR100 | Split<br>Tiny-ImageNet |
| --- | --- | --- | --- | --- | --- |
| 100 | (15,-0.15,1.25) | (15,0.7,1.5) | (15,-0.35,1.0) | (15,-0.95,1.0) | (15,-0.15,1.0) |
| 200 | (15,-0.45,1.5) | (15,0.75,1.1) | (15,-0.7,1.1) | (15,-0.85,1.0) | (15,-0.9,1.0) |

## Appendix D Detailed Experimental Results

We present detailed experimental results for supervised learning from Table LABEL:sub@tab:cls to LABEL:sub@tab:vqa.
Our method consistently performs better than baselines across all tasks and sampling rates.
Meanwhile, several factors prevent us from achieving more significant improvements over the baselines in certain settings:

- •
In high-rate settings for simple datasets, such as the $70\%$ setting for CIFAR10, all methods perform closely to using the entire training set, leaving little room for improvement.
- •
In low-rate settings for challenging datasets, such as the $1\%$ setting for ImageNet-1K, the performance of all methods is limited due to the insufficient number of samples per class.
- •
In scenarios where models are fine-tuned from pretrained weights, the knowledge within in these models anchors the performance at a certain level, leading to similar performance across all methods.

Despite these factors, our method achieves significant improvement in many settings.
For example, it achieves a $5.52\%$ increase in accuracy when selecting $2\%$ of the samples from ImageNet-1K.

**Table 10: Results on image classification. The best one is bold, and the runner-up is underlined.**
| Dataset | CIFAR10 (100%:95.49) | CIFAR100 (100%:77.90) | ImageNet-1K (100%:73.63) |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Sampling rate | 70% | 50% | 20% | 10% | 5% | 2% | 1% | 70% | 50% | 20% | 10% | 5% | 2% | 1% | 70% | 50% | 20% | 10% | 5% | 2% | 1% |
| Random | 94.29 | 92.33 | 84.17 | 71.95 | 59.88 | 45.51 | 35.44 | 74.72 | 70.51 | 52.29 | 37.38 | 23.03 | 13.38 | 8.57 | 71.63 | 69.26 | 58.90 | 47.10 | 34.04 | 16.56 | 5.50 |
| Moderate | 94.04 | 92.36 | 80.96 | 63.91 | 49.94 | 32.00 | 26.18 | 74.61 | 69.95 | 49.37 | 30.53 | 17.68 | 9.28 | 5.97 | 71.33 | 68.72 | 55.23 | 40.97 | 25.75 | 11.33 | 4.52 |
| CCS | 94.23 | 93.83 | 83.85 | 75.56 | 65.89 | 49.02 | 40.24 | 76.10 | 73.12 | 58.39 | 44.92 | 28.68 | 15.93 | 10.28 | 70.74 | 69.23 | 60.04 | 50.41 | 36.92 | 19.92 | 9.43 |
| $\mathbb{D}^{2}$ Pruning | 93.17 | 93.70 | 86.83 | 76.56 | 65.12 | 45.44 | 39.03 | 76.00 | 74.45 | 59.08 | 44.78 | 26.68 | 13.90 | 9.61 | 71.29 | 70.32 | 58.91 | 50.81 | 37.12 | 18.97 | 11.23 |
| GraphCut | 94.38 | 92.43 | 81.98 | 69.29 | 59.36 | 46.93 | 39.68 | 76.64 | 68.79 | 25.08 | 16.46 | 10.78 | 7.84 | 5.94 | 68.91 | 68.72 | 55.28 | 44.79 | 33.54 | 20.07 | 11.49 |
| Entropy | 94.13 | 92.39 | 75.34 | 60.66 | 46.17 | 35.85 | 29.28 | 76.81 | 62.52 | 33.28 | 21.85 | 13.90 | 8.31 | 5.30 | 70.93 | 69.21 | 54.76 | 38.46 | 22.78 | 7.01 | 1.95 |
| Forgetting | 94.76 | 94.34 | 57.72 | 35.21 | 30.87 | 27.22 | 23.62 | 76.64 | 68.75 | 25.17 | 16.45 | 10.70 | 7.82 | 5.90 | 70.57 | 70.46 | 60.77 | 48.73 | 33.86 | 15.13 | 5.66 |
| EL2N | 94.75 | 94.10 | 46.41 | 22.40 | 15.66 | 13.05 | 12.75 | 76.15 | 66.19 | 14.85 | 7.50 | 5.28 | 3.83 | 3.17 | 71.68 | 65.98 | 31.90 | 12.57 | 6.50 | 3.25 | 1.90 |
| AUM | 94.90 | 94.38 | 51.98 | 30.56 | 22.92 | 18.10 | 14.50 | 76.84 | 67.81 | 16.66 | 8.54 | 5.60 | 4.35 | 3.56 | 69.94 | 65.36 | 21.91 | 10.50 | 6.42 | 3.58 | 2.24 |
| Variance | 90.45 | 85.81 | 64.90 | 53.64 | 44.45 | 36.61 | 31.64 | 73.69 | 68.42 | 49.60 | 34.63 | 22.70 | 13.71 | 9.18 | 70.12 | 66.09 | 35.15 | 13.85 | 7.13 | 4.72 | 1.81 |
| SES (Ours) | 95.01 | 94.50 | 88.31 | 80.24 | 69.82 | 54.78 | 45.25 | 77.23 | 74.63 | 61.52 | 48.02 | 33.39 | 19.68 | 14.16 | 72.80 | 71.05 | 63.24 | 53.59 | 41.88 | 25.59 | 13.43 |

**Table 11: Results on text classification. The best one is bold, and the runner-up is underlined.**
| Dataset | ANLI (100%:49.25) | IMDB Review(100%:95.90) |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Sampling rate | 70% | 50% | 20% | 10% | 5% | 2% | 1% | 70% | 50% | 20% | 10% | 5% | 2% | 1% |
| Random | 47.08 | 45.20 | 42.13 | 39.52 | 38.82 | 37.50 | 35.96 | 95.25 | 95.04 | 93.53 | 91.89 | 89.60 | 83.25 | 73.31 |
| Moderate | 46.84 | 45.11 | 41.95 | 40.16 | 38.99 | 35.83 | 33.91 | 95.39 | 95.31 | 94.03 | 92.55 | 90.34 | 58.34 | 50.81 |
| CCS | 46.56 | 45.92 | 41.67 | 41.63 | 40.33 | 37.41 | 36.82 | 95.42 | 95.35 | 93.44 | 91.87 | 89.89 | 85.73 | 82.05 |
| $\mathbb{D}^{2}$ Pruning | 48.56 | 47.49 | 42.77 | 41.43 | 40.34 | 37.92 | 36.29 | 95.43 | 95.40 | 93.75 | 92.44 | 90.77 | 87.40 | 80.06 |
| GraphCut | 46.14 | 44.53 | 42.12 | 39.86 | 38.15 | 35.44 | 34.02 | 95.39 | 95.21 | 93.37 | 91.69 | 90.93 | 86.85 | 82.26 |
| Entropy | 46.32 | 45.53 | 41.45 | 39.67 | 38.54 | 36.69 | 36.40 | 95.39 | 95.17 | 93.92 | 92.57 | 90.30 | 77.16 | 59.41 |
| Forgetting | 48.73 | 42.29 | 39.82 | 38.37 | 35.95 | 35.78 | 35.03 | 95.04 | 95.31 | 93.45 | 89.25 | 53.73 | 57.57 | 51.92 |
| EL2N | 48.70 | 47.85 | 43.14 | 39.63 | 37.52 | 34.33 | 34.27 | 95.29 | 95.34 | 91.31 | 60.29 | 49.88 | 47.18 | 43.74 |
| AUM | 47.86 | 47.58 | 43.57 | 40.02 | 34.66 | 34.16 | 33.62 | 95.27 | 95.23 | 90.60 | 55.68 | 49.81 | 43.13 | 36.29 |
| Variance | 47.97 | 47.87 | 40.70 | 38.75 | 33.52 | 33.50 | 33.17 | 95.44 | 95.40 | 92.34 | 49.76 | 48.95 | 44.90 | 45.53 |
| SES (Ours) | 49.00 | 48.22 | 45.94 | 43.63 | 41.82 | 39.88 | 38.16 | 95.60 | 95.42 | 94.54 | 92.96 | 91.42 | 88.58 | 84.04 |

**Table 12: Results on object detection. The best one is bold, and the runner-up is underlined.**
| Dataset | PASCAL VOC (100%:76.29) |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Sampling rate | 70% | 50% | 20% | 10% | 5% | 2% | 1% |
| Random | 74.02 | 72.10 | 65.45 | 57.56 | 43.47 | 18.78 | 9.24 |
| Moderate | 73.42 | 72.03 | 65.12 | 54.71 | 40.20 | 15.97 | 5.13 |
| CCS | 74.64 | 72.27 | 65.72 | 57.35 | 39.01 | 17.26 | 8.49 |
| $\mathbb{D}^{2}$ Pruning | 74.46 | 72.55 | 65.59 | 55.73 | 44.04 | 19.16 | 10.75 |
| GraphCut | 67.45 | 64.15 | 53.12 | 38.29 | 26.81 | 8.56 | 8.16 |
| AL-MDN | 74.51 | 70.36 | 65.26 | 54.51 | 30.85 | 12.33 | 8.97 |
| SES (Ours) | 75.20 | 73.33 | 66.52 | 59.52 | 45.92 | 23.39 | 16.15 |

**Table 13: Results on visual question answering. The best one is bold, and the runner-up is underlined.**
| Dataset | CC SBU Align (100%:30.40) |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Sampling rate | 70% | 50% | 20% | 10% | 5% | 2% | 1% |
| Random | 29.66 | 29.62 | 29.21 | 29.01 | 28.20 | 25.51 | 25.11 |
| Moderate | 29.96 | 29.67 | 29.53 | 29.11 | 27.30 | 24.85 | 26.54 |
| CCS | 29.93 | 29.90 | 29.94 | 29.91 | 27.71 | 25.31 | 25.59 |
| $\mathbb{D}^{2}$ Pruning | 30.09 | 29.97 | 29.44 | 29.30 | 26.44 | 25.03 | 26.29 |
| GraphCut | 29.86 | 29.73 | 29.53 | 29.11 | 27.30 | 24.85 | 26.54 |
| Instruction | 30.12 | 29.93 | 29.82 | 29.01 | 26.76 | 23.72 | 24.60 |
| SES (Ours) | 30.25 | 30.20 | 30.21 | 30.10 | 28.23 | 27.19 | 27.61 |

## Appendix E Full Qualitive results

Fig. LABEL:sub@fig:app_qua visualizes the results of different methods when selecting $2\%$ of the samples from CIFAR10.
Methods that select the most difficult samples, such as AUM, oversample
near several class boundaries and undersample in several classes that are easier to classify.
Methods that prioritize sample coverage, such as $\mathbb{D}^{2}$ Pruning and CCS, achieve a better sample coverage but may undersample near several class boundaries and fail to preserve the global structure.
Our method well covers the data distribution, providing a set of informative and representative samples for model training.

Figure: (a) Random
Refer to caption: extracted/5903527/pictures/comparison_random-0.02.png

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: Are there anything you can prove about the node-level structural entropy values?
soundness: 3
strengths: Overall, the proposed algorithm is intriguing due to its general empirical performance and some of the novel ideas it introduces. The concept of node-level structural entropy, which quantifies the contribution of an individual node to the global structural entropy of a graph, could be of independent interest. The experiments indicate that the proposed method outperforms existing selection methods in many common learning tasks. Furthermore, ablation studies validate the contribution of each module (node-level structural entropy and importance-biased blue noise sampling) to the overall effectiveness.
summary: The paper studies sample selection which aims to extract a small, representative subset from a larger dataset. The authors introduce a novel sample selection scheme, termed Structural-Entropy-based Sample Selection (SES), which uses and extends the concept of "structural entropy" (Li and Pan, 2016), which assesses how nodes and edges within a graph are hierarchically organized to form multi-level communities. The proposed scheme seeks to address the limitations of existing selection methods, which often prioritize local information and neglect the broader, global context of the samples.

The algorithm begins by constructing a k-NN graph G for the dataset based on similarity. It then calculates the structural entropy value for each node in G (referred to as node-level structural entropy). While structural entropy was originally defined for an entire graph rather than individual nodes, the authors extend this concept using the Shapley value method. Roughly speaking, node-level structural entropy calculates the average increase in structural entropy when a node is added to all potential subgraphs of G. After that, each node is assigned an importance value, which is the product of its structural entropy and training difficulty. An importance-biased blue noise sampling method is then used to select samples. instead of sampling solely based on importance scores, this sampling process prevents the selection of overly similar samples, thus maintaining diversity within the selected subset.

The effectiveness of the SES scheme is demonstrated through experimental studies and compared to other selection methods in various tasks such as supervised learning, active learning, and continual learning.
weaknesses: I believe the results could benefit from stronger theoretical justification. While the high-level ideas are reasonable, the mathematical properties are not mentioned in this paper. A deeper discussion on these aspects should be provided. Especially I am interested in what are the mathematical properties of the node-level structural entropy.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: 1, The construction method of the Encoding tree is challenging. The author mentioned the Huffman tree construction; how does this affect the conclusions of this article?

2, Equation (5) in the paper calculates the overall importance score of the node. Is this importance score node-wise or point-wise sampling? A data point may appear in multiple nodes, does this affect the proposed sampling method?

3, Have you considered other ways of combining global structural entropy and local training difficulty indicators, rather than through the multiplication method (S(u) = Se(u) * St(u))?

4, Can you provide more theoretical explanations or proofs to demonstrate why structural entropy, as a global indicator, is helpful for considered tasks (e.g. supervised, active, and continual learning)?
soundness: 2
strengths: 1, The method utilizing the encoding tree effectively measures local structural information across different scales, providing valuable insights.  Various experiments on different learning tasks demonstrate SES’s effectiveness.

2, Structural entropy is decomposed from the overall graph level to individual nodes, resulting in a node-level definition of structural entropy. By leveraging properties of the Shapley value, authors show that the Shapley value of a node can be computed in linear time relative to the number of edges.
summary: The paper proposes a Structural-Entropy-based sampling (SES) method for data selection. This approach integrates global structural information, quantified using structural entropy, and local information (training difficulty) to choose informative and representative samples for training. The authors show that  incorporating global structural information can improve the quality of sample selection. Traditional methods often focus on local data properties, such as training difficulty, while ignoring broader connectivity patterns. SES constructs a sample graph using k-nearest neighbor (kNN) relationships to model sample similarity and applies structural entropy at a node level to evaluate each sample’s significance in preserving the overall data structure.
weaknesses: 1, The overall idea is relatively simple and incremental, mainly based on the concept from Li and Pan 2016. Also, the proposed method is very heuristic without solid theoretical validation. For example, in line 212-213, "Given our emphasis on ..., we only use....". Can you give more detailed explanation? In my opinion, this is not a serious claim for a research article.  In line 352, you say "10X speedup" because you use only 10\% of dataset. Can you provide the realistic experimental time for this claim? Do you count the construction time of your sample? 

2, While the Shapley value of a node can be computed in linear time relative to the number of edges, the edges in a kNN graph is O(k|X|). It is still  time consuming to calculate the Shapley values for all nodes of the encoding tree, especially for large dataset.

3, The author does not clearly explain why preserving the global structure of the dataset is beneficial or provide theoretical guarantees regarding its impact on performance in tasks such as supervised, active, and continual learning. Similarly, the rationale for prioritizing samples with high local information (i.e., training difficulty) is insufficiently justified.

4, The blue noise sampling method effectively promotes diversity, yet the balance between selecting challenging samples and maintaining sample diversity could be further clarified. A comparative analysis with methods that explicitly optimize for diversity, such as clustering-based selections, would help to clarify the advantages of SES.

5, The method relies on the quality of the embedding used to construct the kNN graph. If the embedding representation is poor, structural entropy may not accurately capture the global structure of the data.

6, Some experimental parts are not sufficient. For example, in the continual learning part, they only consider three baselines and two memory sizes (100, 200). Moreover, do you consider both Class-Incremental Learning and Task-Free Continual Learning?

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Please see the weaknesses.
soundness: 2
strengths: 1.The writing of this paper is good and easy to follow.

2.This paper has a certain degree of innovation, introducing a structural entropy as a global metric for sample selection.
summary: This paper proposes a novel sample selection method that can capture both local and global information of data simultaneously. Specially, first, they use a $k$-NN to construct the sample graph of original data. Second, they employ structural entropy to measure global information and use training difficulty to capture the local information of the graph. At lats, they utilize the importance-biased blue noise sampling to select a set of diverse and representative samples. 

The main contribution of this paper is to propose a new global metric for sample selection.
weaknesses: 1. Hypergraphs [1] can capture more complex relationships, and I believe that if the authors had used hypergraphs instead, the results would have been even better. I would be delighted to see the authors add new experiments to verify my hypothesis.

2. How would the authors define informative and representative samples? They mention these concepts multiple times, but do not provide a detailed explanation.

3. Taking sample as a node is not very reasonable, as it treats the sample as a whole and ignores the local information contained in the sample itself. Perhaps using a Hyper-class representation [2] would yield better results. I would be delighted to see the authors conduct new experiments to verify my hypothesis.

4. The experimental results do not show the variance, so I hope the authors can make up the variance.

5. Just a little confused, why most of the comparison algorithm's experimental results are not as effective as random selection? So what's the meaning of those comparison algorithms? Or are those comparison algorithm chosen by the author appropriate? Are the parameters of the those algorithms not optimally tuned?

6. The effect of blue noise sampling (BNS) is not as good as message passing (MP) when the sampling rate is greater than or equal to 20%, why not directly use MP? Simply because BNS does not require hyperparameter tuning, it sounds far-fetched.

7. As can be seen from Figure 4, (b) has better boundary division, while (c) has several categories of samples grouped together. It seems that (b) is better. How can we understand this phenomenon?

[1] Learning with hypergraphs: Clustering, classification, and embedding.

[2] Hyper-class representation of data.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Please see Weaknesses.
soundness: 2
strengths: 1. The idea is interesting and reasonable.
2. The experiments are sufficient and the experimental results are good.
summary: This paper proposes a sample selection method with structural entropy. It first introduces the structural entropy of a graph into the sample selection task, and then applies the Shapley value to decompose the structural entropy of a graph to the node-level structural entropy. At last, it designs a score for sample selection with the node-level structural entropy.
weaknesses: 1. The main techniques used in this paper are all existing methods, e.g. the structural entropy and Shapley value. The paper seems an application of these techniques in the sample selection task. The paper should clarify its novelty and technical contributions.

2. The paper derives Eq.(3) from the Shapley value, and then removes the second term, leading to Eq.(4), which is used in the method. However, the motivation is unclear. Why should we remove the second term? What is the advantage of removing this term? The ablation study of this term should be conducted in the experiments. The paper only claims that they want to design a global metric and the second term is a local metric. I do not think it's convincing enough. What is the advantage of only considering global information? Moreover, in Eq.(5), the method combines the global score S_e and the local score S_t. It seems a little contradictory. In Eq.(4), they do not want the local term but in Eq.(5) they need the local term. It seems strange and not well-motivated.

3. Eq.(5) needs more justification. Why should we multiply S_e and S_t? What is the advantage? Why not just sum S_e and S_t, or combine them with other forms? I think more ablation study is needed to justify the effectiveness of Eq.(5).

4. In the experiments, the experimental setup should be introduced in more detail. For example, what is the difference between the supervised setting and the active learning setting? They both need to select some samples to train the model and then is used to predict the test data.

Meta-review: The reviewers raised several concerns during the review process regarding largely around lack of novelty and lack of theoretical justification. The authors have addressed most of these concerns. In my opinion the work is somewhat incremental, but the empirical results are interesting and the overall consensus is towards acceptance.

Decision: Accept (Poster)