Structural-Entropy-Based Sample Selection for Efficient and Effective Learning
Authors: Tianchi Xie
Jiangning Zhu
Guozu Ma
Minzhi Lin
Wei Chen
Weikai Yang
Shixia Liu
Venue: ICLR 2025 Poster (2025)
Keywords: Sample selection
graph
structural entropy
blue noise sampling
Primary area: other topics in machine learning (i.e., none of the above)

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 $\textbf{S}$tructural-$\textbf{E}$ntropy-based sample $\textbf{S}$election ($\textbf{SES}$), a method that integrates both global and local information to select informative and representative samples. SES begins by constructing a $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.

Published as a conference paper at ICLR 2025
STRUCTURAL-ENTROPP-BBNN SAMPLE SELECTION FOR EFFICIENT AND EFFECTIVE LEARNING
Tianchi Xie Jiangning Zhu' Guozu Ma², Minzhi Lin'
Wei Chen², Weikai Yang".f, Shixia Liu
BNRist, Tsinghua University "China Telecom Wanwei Information Technology Co., Ltd á Miicosooft Research 'Hong Kong University of Science and Technology (Guangzhou)
ABSTRACT
Sample selection improves the efficiency and effectiveness of machine learning models by providing informative and representative samples. Typically, samples can be modeled sample graph, where nodes are samples and edges represent their similarities. Most existing methods are based on local information, such as the training difficultyy 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 Structural- Structurl-EEnrroyy Entropy
sample Selection (SES), a method that integrates both global and local information to select informative and representative samples. SES begins by constructing a &NN-graph among samples based on their similaritics. It then measures sample importance by combining structural entropy (global metric) with training difficulty (local metric). Finally, SES applies importance-biant noise sampling to select of diverse and representative samples. Comprehensive experiments in three learning scenarios supervised learning, active learning, and continual learning clearly demonstrate the effectiveness of our method.
blue
INTRODUCTION
Data budgets that limit sample sizes are pervasive in machine learning applications (Liu al. 2025). For example, researchers and practitioners often face limited annotation and computational resources, necessitating the use of fewer samples to enhance efficiency. Similarly, in continual learning scenarios (Hou et al., (019), the memory constraint requires fewer samples from previous tasks to retain knowledge effectively. 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. Informative samples are those that significantly reduce model uncertainty and crucial for improving the accuracy and robustness the training process, while representative samples are those that preserve the diversity and overall distribution of the dataset (Huang al. 2014). 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 local information, such as the training difficulty and the node degree (Maharana et al.) 2024). 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] 2006) and has been shown to effective improving the representativeness of selected samples (Zhang et al. 2023 Yuan et al. 2021 Zhao et al., 2021). Therefore, we aim incorporate global information into the sample selection process to improve the quality of the selected samples.
"Equal contribution. Corresponning author.

---

Published as a conference paper at ICLR 2025
The key to incorporating global information is to identify which specific metric(s) can accurately capture the global structure of the sample graph. Entropy is a class of metrics well-suited for this purpose, as it quantifies both informativeness and representativeness (Pan et al., 2005 Li & Guo 2013). In particular, [i & Pan (2016) propose structural entropy to evaluate the amount of information required 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 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 challenge in decomposing this metric to the level of individual nodes, limiting its utility for fine- fine-grained, node-level selection.
To address this challenge, use the Shapley value (Shapley 1951), 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-consuning as it requires exponential-tina computation to enumerate possible subgraphs. To accelerate this, we reformulate the Shapley value for structural entropy, enabling linear-time calculation with respect to the edge number. Based on this reformulation, we propose node-level structural entropy metric that effectively measures the importance of nodes in preserving the global structure. Building on the decomposition, we present
sample Selection (SES) method that integrates both global and local metrics to select informative and representative samples. This method begins by constructing a A: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-biant blue noise sampling method is employed to iteratively select 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 oottt--ffthe--eet 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:
We propose node-level structural entropy metric that quantifies the importance of nodes in preserving the global structure, and it can be calculated in linear time.
We develop urructual-eentropy--e based sample selection method that integrates both global and local metrics to select informative and representative S
We conduct experiments in supervised learning, active learning, and continual learning that demonstrate the effectiveness of our method.
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-bast methods.
Attribute-basee 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.] (020) and the variance of the predicted probabilities across training epochs (Swayamdipta et al.) 2020). Metrics that measure model error include EL.2N (Paul et al. 2021). which calculates the L2 norm of the error vector, and the Forgetting score TToeva al. 2019), which tracks the frequency of misclassification after initial correct classifications. AUM (Pleiss et al. 2020) combines both perspectives by measuring the confidence for correct classifications and the error for misclassifications, Based on these metrics,
'The implementation is available http:://giitth..coom//eerss////s sample selection
2

---

Published as a conference paper at ICLR 2025
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 the model performance (Paul et al., (021). However, this method overlooks easy samples, which are crucial for model training when data budgets are limited (Sorscher et al. 2022). To address this issue, CCS (Zheng et al. 2022) divides the dataset into strata based training difficulty and performs random sampling within each stratum. InfoBatch (Qin et al. 2023) 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. 2019 Killamsetty jtt al. 202T). However, these gradients depend on the model's 's current state during training, limiting the applicability of the selected samples to other models.
Connection-basee methods utilize local connections within the sample graph to optimize sample diversity and coverage. GraphCut (Iyer et al., (021) selects samples with weak connections among them to promote diversity while maintaining strong connections to unselected samples for better coverage. Moderate coresct (Xia et al., 2023) selects samples based on their distances from the class centers. To enhance the generalizability across different scenarios, samples near the median distance selected. D Pruning (Maharana et al. 2024) aims to select difficult and diverse samples. 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) iet al. 2021). Overlooking this global information can lead to suboptimal learning performance. To address this gap, we propose structural-enie penttuurll-ettoo--baeeeee sample selection method that integrates both global and local metrics to select informative and representative samples.
3 BACKGROUND: STRUCTURAL ENTROPY OF GRAPH
Structural entropy evaluates how the nodes and edges in a graph are hierarchically organized to form communities different levels (Li & Pan 2016). Thus, it is effective in globally quantifying the community structure of the graph regarding its overall connectivity patterns. The calculation of structural entropy based on an encoding tree that represents the graph's 'ss hierarchical community structure. In this tree, each node represents a community, and each Icaf node corresponds to graph node that forms 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. [ shows an undirected, weighted graph G and its encoding tree T. The entropy is calculated for each non-root node 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-commen commumiy connections and sparser inter-community connections. The intra-community connection, (a)) is quantified by the total weighted degrees of the nodes, while the inter-community connection, g(x), is quantified by the total weight of the edges with exactly one endpoint in the community (outer edges). Given an encoding tree T, the structural entropy of G is the aggregation of the entropy values from all its non-root nodes:
H(G,T)== -- Σ g(a) log vol(a.
(V) vol(a-))
aET
where a is a non-root node, at is its parent node, g(a) is the total weight of its outer edges, and vV)(V), vol(a), vol(a represent the total weighted degrees of the nodes V, a, and a
Graph G
Encoding tree T
0.6
community
0.6
0.5
0.
0.9
g(a)= 0.5+0.6
0.5
0.8
vol(a)
Figure 1: The structural entropy calculation for an undirected, weighted graph.
3

---

Published as a conference paper at ICLR 2025
In applications, the encoding tree T may be unknown. To best capture the hierarchical community structure in such cases, the encoding tree T is constructed by minimizing the structural entropy. Obtaining an exact solution for the minimization is challenging, so greedy methods similar to the Huffman tree construction have been developed (Li & Pan, 2016: Zhu et al.] (023). We demonstrate in Appendix tAattat the choice of the construction method has negligibl effect on the sample selection results. Therefore, we use the most recent method proposed by Zhu et al. (2023).
4
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 uniquely 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, and v, is their cosine similarity normalized [Ó. 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 local metric, training difficulty, to assign an importance score to each sample. Using this score, we develop an importance-biasee 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 the node level. While local metrics 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 2016). making 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-Ievel structural entropy to the node level.
Chen & Teng (017)) have shown that the Shapley value (Shapley 1951) 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 node 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, calculate the node's contribution to these subgraphs. Formally, let Vs denote subset of the node set V, the Shapley value of node u is:
ddu)
1
Σ
(ML-1)
-1 (MIGTVV U (u)I.T) - -H(G(s)).)
V
V.V
where G[Vs] is the subgraph of G' that consists of nodes in Vs and the edges between them, and (V-11) is the binomial coefficient.
[Val
Directly calculating Eq. (2) requires an enumeration of all possible subgraphs of G, which becomes intractable for 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 (V, E, W) be undirected, weighted graph. The Shapley value of node is
((u)
1
Σ (a.D)E
Wa.v log vol(vv)))) d(u)) log log
(V)
where w.,, is the weight of edge (u, v), auve is the least common ancestor of node u and in the encoding tree T, and d(u) is the weighted degree of node
4

---

Published as a conference paper at ICLR 2025
Quev
Ouee'
voll(ssw)
vollaur))
(b)
Figure 2: Edges connecting: (a) nodes and u across different communities; (b) nodes u and v' within the same community.
The proof of Proposition iis provided in Appendix B It indicates that the Shapley value can be calculated in linear time with respect to the edge number. Thus, this reformulation enables an efficient and exact calculation. Eq. (3) 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. Due to the below theoretical and empirical advantages, we only use the first term to define the node-level structural entropy (S,):
Σ Sc(u) vol(V) (u.D)E
Wu, log vol((ave)))
(4)
As this definition is related to sample coverage. the first theoretical advantage lies in its ability to enhance model performance. Following previous work (Zheng et al. 2022), we assume that samples are drawn from a distribution P, with probability measure μu, and quantity the sample coverage as P(u, r) SB(u.r) dp(xr), where B(u, r) is a r-radius ball centered u. We demonstrate theoretically and empirically that (u) provides a lower bound for sample coverage:
1 ([S((()) KR
nk exp
- [[[Pu,r)),
(5)
where n is the number of samples, & is the parameter in kNN-graph construction, and R the upper bound of edge weights. This result indicates that maximizing Se(u) during selection inherently improves sample coverage. Given the strong correlation between coverage ability and the empirical loss (Zheng al. 2022). , selecting samples with high node-level structural entropy enhances model performance. The mathematical proof and the empirical validation are detailed in Appendix C
The second theoretical advantage is its ability in maintaining the overall graph structure. A higher (alv))))) indicates that the edge (u, v) connects the nodes that are more distantly located in T. For example, in Fig. [ the edge (u, o²) stays within the same community while the edge (u, v) spans different communities, resulting in a higher vol (avv). Thus, vol effectively quantifies the extent to which an edge bridges different communities. Since (z(u) is the weighted sum of (aave). nodes with high structural entropy serve as boundaries between communities. Selecting these nodes is crucial for maintaining the overall structure of the graph.
The empirical advantage of this definition is demonstrated through an ablation study, detailed in Appendix G The results show that only using the first term slightly improves performance.
4.2 IMPORTANCE- BIASED BLUE NOISE SAMPLING
To select 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,) is effective local metric in quantifying the sample's 's impact model performance, as difficult samples are typically more informative for improving the decision boundary (Paul et al.) 2021; Sorscher al. 2022). Therefore, we employ it the local metric. Accordingly, the overall importance score (S) is combination of node-level structural entropy and training difficulty:
S(u) (.) S.(u).
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. 2022). An alternative is the message passing mechanism employed by 2 Pruming: once a sample is selected, this method sends weighted messages to decrease the importance scores of its neighbors in the graph. However, the message
5

---

Published as a conference paper at ICLR 2025
weights sensitive 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 al. 2019 Liu et al., 2018). This method increases sampling in low-density regions, which enhances the diversity of the selected samples. Consequently, we develop an imporance-bbassed blue noise sampling method select 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 threshold 0; otherwise, accepting iteratively until no more samples can be selected. To determine the threshold for given sampling rate, we perform binary search on O.
selected sample. These two steps are performed
5 EXPERIMENTS
In this section, 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, conduct qualitative analysis of the selection results.
5.1
SUPERVISED LEARNING
In supervised learning tasks, 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, CIFARIO, CI-
FAR100 (Krihevskyy 2009), and ImageNet- IK (Deng et al. 2009). Following Maharana et al. (0224)
ResNet- 18 (He et al. 2015) is used for CIFAR 1Ô and CIFART00, while ResNer-34 (He et al. 2015) used for ImageNet- IK. 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. 2020 which focuses on natural language inference, and the IMDB Review dataset (Maas et al. 1011), which focuses sentiment analysis. Following Maharana et al. (204)), we fine-tune the RoBERTa model (Liu et al. 2019) and report the accuracy the test set for both datasets.
For object detection, we use the PASCAL VOC dataset (Everingham et al. 2010). which contains
bounding box annotations of objects and animals. Following Choi et al. (2021), , train SSD (Liu et al. 2016) with VGG-16 (Simonyan & Zisserman 2015) backbone from scratch and report the mAp the test set.
For visual question answering, we use the CC SBU Align dataset (Zhu et al. 2024). which con- tains high-quality, aligned image-text pairs. Following Wei et al. (2023), ) we fine-tune MiniGPT- 4 (Zhu et al.) 2024) on this dataset, and report the average accuracy of the model on five datasets:
OKVQA (Schwenk et al.) 2022). IconVQA (Lu al. 2021). DOA (Mathew et al., 2021).
GQA (Hudson & Manning 2019). and ScienceQA (Saikh et al. 2022).
Please refer Appendix for more details on the dataset statisties 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) Random selection of samples. 2) Moderate coreset (Xia et al. 2023).33 3) CCS Zheng al., (022), 4) 2D2 Pruning (Maharana et al. 2024), and 5) GraphCut (yerr al. 2021) For image classification and text classification, the task-specific baselines include selecting the most difficult samples based on: 1) Entropy (Coleman et al. 2020 2) Forgetting score (Tneva et al. 2019), 3) EL2N (Paul al. 2021), 4) AUM (Pleiss et al. 2020). and 5) Variance (Swayamdipta et al. 2020). We also include two widely used baselines that prioritize diversity in sample selection, including k-means (Xu et al. 2003), which selects the samples closest to k k-means clustering centers, and k-DPP (Kulesza & Taskar] (201)), b, which employs a determinantal point process to encourage diversity. For object detection, include selection based on the AL-MDN uncertainty (Choi et al.

---

Published as a conference paper at ICLR 2025
Table Results for supervised learning on: (a) ImageNet- IK; (b) ANLI; (C) PASCAL VOC: (d) CC SBU Align. The best one is bold, and the runner-up is underlined.
(a) IetgeNet-IK
(b) ANLI
Dataset
ImageNet-1K
(100%:73.63
Datasel
ANLI
(1005:49:25)
Sumpling rate
70%
50%
20%
10%
5%
2%
1%
Sampling rate
70%
50%
20%
10%
5%
2%
1%
Random
71.63
69.26
58.00
47 17:10
14.04
16.56
5.50
Random
47.08
45.20
42.13
59.53
18.82
37.50
35.96
Moderute
71.33
68.72
55:23
40.97
25.75
11.33
4.52
Moderate
46.84
45.11
41.95
40.16
38.99
35.83
33.91
CCS
70.74
69.25
60.04
50.41
36.92
19.92
9.43
CCS
46.56
45.92
41.67
41.63
40.33
37.41
36.82
D Pruning
70.32
50.81
37.12
18.97
D Pruning
48.56
47.49
41.43
40.34
32.92
36.29
GruphCut
68.91
68.72
33.54
20.07
11,49
GraphCut
48.53
39.56
35.15
35.46
Fatrooy
70.93
69.21
54.76
79
7,01
1:95
Entropy
46.32
45.55
41,45
39.67
38.54
Forgedtnn
70.57
70.45
60.77
48.
33.86
15.13
5.66
Forgetting
48.73
42.29
39.82
38.37
35.95
35.78
35.03
F1.2N
71.68
65.98
31.90
12.57
6.50
3.25
1,90
F1.2N
48.70
47.85
43.14
39.63
37.52
34.35
34.27
AUM
09.94
65.35
21.91
10.50
6.42
3.58
2.24
AUM
47.86
47.58
43.57
40.02
34.66
34,16
33.62
Varfance
70.12
66.09
35.15
13:85
7.13
4.72
1.81
Varfance
47.97
47.87
40.70
38.75
33.52
33.50
33.17
k-amcans
69.47
9.65
k-means
46.48
46.52
39.89
k-DPP
70.84
k-DPP
40.98
16.66
(Ours)
72,80
71.05
53.59
41.88
25.59
(Ours)
48.22
43.63
41.82
39.88
(c) PASCAL VOC
(d) CC SBU Aligm
Dataset
PASCAL VOC (16.2977..9)
Dataset
CC SBU
Align (100%:30040)
Sampling rate
78%
50%
20%
10%
5%
2%
1%
Sampling rate
70%
50%
20%
10%
5%
25%
1%
Random
14,02
12.10
65:45
57.56
43.47
18.78
9.24
Randona
29.66
29.62
29.21
29.01
28.20
25.51
Maderate
73.42
72.03
54.77
40.20
5.13
Maderate
29.1
17.30
CCS
24.64
12.27
65.72
39.01
17.26
CCS
29.93
29.90
29.91
27.71
25.59
D Pruning
74.46
72.55
65.59
55.73
44.04
19.16
10.75
D Pruning
30.09
29.97
29.44
29.30
26.44
25.05
26.29
GraphCot
67.45
64.15
53.12
38. 70
26.81
8.56
8.16
GraphCot
29.86
29.73
29.51
29.11
27. 30
24.85
26.54
AL-MDN
74.51
70.35
65.26
54.51
30.85
12.33
8.97
Instraction
20.12
29.95
29.82
29.01
26.76
23.72
24.50
k-meens
74.22
72.35
65:52
01
43.35
16.96
5.16
k-meuns
29.78
29.61
29.54
99.20
27.72
25:47
25.80
k-DPP
74.19
71.99
86.00
43.92
18.20
k-DPP
29.27
26.13
(Ours)
75.20
73.33
45.92
(Ours)
30.25
30.20
28.33
27.61
2021), which captures the detector's 's overall uncertainty for an image. For visual question answering. we include selection based on the Instruction score (Wei et al., (2023). which evaluates an image-text pair based on image-text matching degree and text length.
Implementation. For all tasks, we extract image embeddings using CL.IP (Radford et al. 2021 and text embeddings using Sentence-BERT (Reimers & Gurevych (219)) due to their demonstrated performance in capturing the semantic similarities. 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 Appendix G and observe no significant performance difference among them. We also perform a grid search on the hyperparameters, such k in the &NN-graph construction (see Appendix B for details).
5.1.2 RESULTS
To cover 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 runs. Table I shows the results on four datasets that cover all the four tasks. The full results are provided in Appendix [F]
Baselines that select the most difficult samples, such as AUM and Forgetting, perform well in high- sampling-rate settings. However, these methods fall behind in low-sampling-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. 2022). Methods that prioritize sample coverage, such as CCS and ID² Pruning, address this issue and perform well in now-sampling-ras settings. However, in high high-sampling-raun 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. Methods that prioritize diversity are competitive in wow-samlling-aat settings because they ensure the coverage of the dataset. However, in high-samplingg-att settings, they face challenges in balancing diversity with sample importance, leading to 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 representativennss. 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
7

---

Published as a conference paper at ICLR 2025
Table ((d).
achieve 10x speedup by using only 10% of the dataset fine-tune MiniGPT-4, with only a 0.3% drop in accuracy compared to using the entire dataset. Specifically, our method reduces the fine-tuning time single Nvidia Tesla V100 GPU from approximately 30 minutes to minutes, adding only a negligible selection overhead seconds.
5.2 ACTIVE LEARNING
Active learning (Settles 2009) aims to reduce annotation effort by selecting a set of informative and representative samples from unlabeled pool. These samples are then labeled to train models. The key difference between active learning and supervised learning lies in the absence of labels during sample selection, which makes the selection process more challenging.
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- IK. 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- IK validation set.
Baselines. We include the baselines from Sec. [. that are applicable to unlabeled datasets. Addition- ally, include Prototypicality (Sorscher al. 2022) 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 more ambiguous than the samples closer to the center.
Implementation. In the active learning scenario, using 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, extract the image embeddings with self-supervised model, SWAV (Caron et al., 2020). 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 random seeds in Table 2 In low-sampling-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, random selection and other baseline methods. This is because structural entropy compensates for missing labels by capturing the community structure in the datasets.
method consistently performs better than
5.3 CONTINUAL LEARNING
Continual learning KKirkparrik et al. 2017) 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. 2019), which selects small set of informative and representative samples from previous tasks and replays them during the training of new tasks.
5.3.1 EXPERIMENTAL SETUP
Datasets and models. We use the datasets commonly used in continual learning, including Permuted MNIST, Split MNIST, Split CIFARIO, Split CIFARI00, and Split Tiny- ImageNet. Permuted MNIST Table 2: Results for active learning. The best one is bold, and the runner-up underlined.
Dataset
ImageNet- IK (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
56.08
40.99
24.30
7.90
2.46
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
8

---

Published as a conference paper at ICLR 2025
Table 3: Results for continual learning, The best one is bold, and the runner-up is underlined.
Permuted MNIST
Split MNIST
Split CIFARIO
Split CIFARTO0
Split
Dataset
TinyeemageNNe
Memory size
100
200
100
200
100
200
100
200
100
200
D Pruning
78.25
79.94
96.79
97.69
64.54
66.08
$1.86
54,50
19.08
19.50
GruphCut
76.98
78.61
91.34
94.25
61.02
61.66
53.35
54.66
19.76
20.53
k-center
78.17
79.75
94.39
96.61
61.47
62.74
51.16
53.10
18.87
18.90
Grudient Matching
77.30
79.27
95.39
97.54
61.65
62.65
54.13
56.29
19.19
19.00
FRCL
77.33
94.48
97.10
62.93
54.28
18.86
19.01
iCaRL
28.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. 02.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
39.69
20,80
21.20
splits MNIST (LeCun et al. 1998) into 10 segments, where a fixed permutation of the pixel order applied to all images in each segment simulate different distributions. Thus, it contains 10 classification tasks with samples from different distributions. The other four datasets split the image classes in MNIST, CIFARIO 10, CIFAR 100, and Tiny-ImageNet (Le & Yang 2015) into 5, 20, and 20 segments, respectively, and each segment corresponds to a different classification task. In aligmment with prior studies (Borsos et al. 2020 Hao et al., 2024). 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 CIFARIO, and ResNet-18 with multi-head output (Zenke et al.. 2017) for Split CIFAR 100 and Split Tiny- ImageNet. We conduct the experiments under three settings: class-incremental, nek-incrrmenntl, and task-free (Wang et al. 2024). In the task-incremental setting, the models are trained sequentially for each task while maintaining 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 used, with the replay samples weighted by hyperparameter that controls their influence. After each task is completed, samples are selected from the current task replace portion of the replay memory. We report the average accuracy all tasks, with the model unaware of a sample's 's task during testing. The other two settings are introduced in Appendix F
Baselines. We include baselines from Sec. to select samples that update the replay memory. Ad- ditionally, we include nine widely used selection methods for continual learning: 1) k-center (Sener
& Savarese 20188. 2) Gradient Matching (Campbell Broderick 2019). FRCL (Titsias et al.
2020). 4) iCaRL (Rebuffi et al. 2017). 5) Greedy Coreset (Borsos sos et al., 2020). 6) BCSR (Hao
al.
2024). 7) DER++ (Buzzega al. 2020), 8) GSS (Aljundi et al. 2019 and 9) GCR (Twaari
et al.
2022 Detailed introduction of these methods is provided in Appendix F
Implementation. We extract the image embeddings with CLIP and measure training difficulty with AUM. For all baselines and our method, we perform grid search on the weight of replay samples to determine its optimal value (see Appendix D for details).
5.3.2 RESULTS
We test replay memory sizes of 50, 100, 200, and 400 and report the results averaged over 5 random seeds. Due to space limitations, Table 3 shows the results for replay memory sizes of 100 and 200 under the class-incremental setting, excluding baselines from Sec. 5. that neither the best nor the runner-up in any dataset or memory size. The full results are provided in Appendix F Our method consistently achieves better performance than basclines 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 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

---

Published as a conference paper at ICLR 2025
5.4 ABLATION STUDY
We conduct ablation studies on supervised learning using CIFARIO to evaluate the impact and behavior of each module in our method. This section presents results the effect of modules. Additional ablation studies are provided in Appendix G
Effect of modules. We ablate the two key modules our method, node-level structural entropy (SE) and importance-biasee 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 D2 pruning. The hyperparameter controlling message weights in MP is determined through grid search as in the original paper (Maharana al.) 2024). Table 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 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 the time-consuming grid search on the additional hyperparameter, demonstrating its effectiveness.
5.5 QUALITATIVE ANALYSIS
We visualize the selection results of different methods when selecting 2% of the samples from CIFARIO by projecting them onto a swo-dimensional plane using t-SNE (van der Maaten & Hinton 2008 Fig. shows the results of AUM, mD2 Pruning, and our method. Each point is a selected sample, and the colored contours indicate the high-density regions for each class. The full results are provided in Appendix H Methods that select the most difficult samples, such as AUM, oversample near several class boundaries and undersample in several classes that are casier to classify (Fig. B()). Methods that prioritize sample coverage, such as D Pruning, achieve a better sample coverage but still miss critical samples near class boundaries (Fig, B(b).. This gap indicates that these methods may not effectively preserve the global structure of the samples. Our method well covers the data distribution, providing set of informative and representative samples for model training (Fig.
Oversample near these boundaries
Undersample these classes
Undersample near these boundaries
Well cover the data distribution
(a)
(b)
(c)
Figure 3: Visualizations of results when selecting 2% of the samples from CIFARIO using: (a) AUM; (b) 2 Pruning; (c) our structural-entropy- based sample selection method.
6 CONCLUSION
In this paper, we present senuutuurllentroo--balel sample selection method for efficient and effective learning. The key idea behind our method decompose graph-level structural entropy to a node- level global metric using the Shapley value. This global metric is combined with local metric, training difficulty, for selecting informative and representative samples. The effectiveness of our method is validated by comprehensive experiments in 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 wider range of tasks, such infographics VQA (Mathew et al. 2022) and building foundation models (Yang et al. 2024). Third, applying techniques such as hyper-class representation (Zhang al. 2022) to enhance the image and text embeddings can improve the quality of selected samples.
10

---

Published as a conference paper at ICLR 2025
7 ACKNOWLEDGEMENTS
Tianchi Xie, Jiangning Zhu, Minzhi Lin, and Shixia Liu are supported by the National Natural Science Foundation of China under grant A2142049 and in part by the Tsinghua University-China Telecom Wanwei Joint Research Center. The authors would like to thank Duan Li, Yukai Guo, and Zhen Li for their valuable discussions and comments.
REFERENCES
Sameer Agarwal, Kristin Branson, and Serge Belongie. Higher order learning with graphs. In Proceedings of the International Conference Machine Learning, pp. 17-24, 2006.
Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio. Gradient based sample selection for online continual learning. Advances in neural information processing systems, 32, 2019.
Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. In Proceedings of Advances in Neural Information Processing Systems, pp. 14879-14890, 2020.
Pietro Buzzega, Matteo Boschini, Angelo Porrello, Davide Abati, and Simone Calderara. Dark experience for general continual learning: strong, simple baseline. Advances neural information processing systems, 33:1 13:15920-15930 2020.
Trevor Campbell and Tamara Broderick. Automated scalable bayesian inference via hilbert coresets. Journal of Machine Learning Research, 20(15):1-38, 2019.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. In Proceedings of Advances in Neural Information Processing Systems, pp. 9912-9924, 2020.
Wei Chen and Shang-Hua Teng. Interplay between social influence and network centrality: A comparative study on shapley centrality and mangle-node-nfluenne centrality. In Proceedings of the international conference on world wide web. pp. 967-976, 2017.
Jiwoong Choi, Ismail Elezi, Hyuk-Jae Lee, Clement Farabet, and Jose M. Alvarez. Active learning for deep object detection via probabilistic modeling. Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 10264-10273, 2021.
Cody A. Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter D. Bailis, Percy Liang, Jure Leskovec, and Matei A. Zaharia. Selection via proxy: Efficient data selection for deep learning. In Proceedings of the International Conference on Learning Representations, 2020.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 248-255, 2009.
Mark Everingham, Luc Van Gool, Christopher K. Williams, John M. Winn, and Andrew Zisserman. The pascal visual object classes (yoc) challenge. International Journal of Computer Vision, 88(2): 303-338 2010.
Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. In Proceedings of the AAAI conference on artificial intelligence, pp. 3558-3565, 2019.
Bernd Fritzke. A growing neural gas network learns topologies. In Proceedings of Advances in Neural Information Processing Systems, pp. 625-632, 1995.
Samir Yitzhak Gadre, Gabriel Ilharco, Alex Fang. Jonathan Hayase, Georgios Smyrnis, Thao Nguyen, Ryan Marten, Mitchell Wortsman, Dhruba Ghosh, Jieyu Zhang, et al. Datacomp: In search of the next generation of multimodal datasets. Proceedings of Advances Neural Information Processing Systems, 36, 2024.
11

---

Published as a conference paper at ICLR 2025
Chengeheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: A comprehensive library for coreset selection in deep learning. In Proceedings of International Conference on Database and Expert Systems Applications, pp. 181-195, 2022.
Jie Hao, Kaiyi Ji, and Mingrui Liu. Bilevel coreset selection in continual learning: A new formulation and algorithm. In Proceedings of Advances in Neural Information Processing Systems, pp. 51026- 51049, 2024.
Kaiming He, Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
770-778, 2015.
Saihui Hou, Xinyu Pan, Chen Change Loy, Zilei Wang, and Dahua Lin. Learning a unified classifier incrementally via rebalancing. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 831-839, 2019.
Sheng-Jun Huang, Rong Jin, and Zhi-Hua Zhou. Active learning by querying informative and representative examples, IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(10); 1936-1949, 2014.
Drew A. Hudson and Christopher D. Manning. GQA: A new dataset for real-world visual reasoning and compositional question answering. Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 6693-6702, 2019.
Rishabh Iyer, Ninad Khargoankar, Jeff Bilmes, and Himanshu Asanani. Submodular combinatorial information measures with applications in machine learning. In Proceedings of the International Conference Algorithmic Learning Theory, pp. 722-754, 2021.
Ariel Jaffe, Yuval Kluger, George C. Linderman, Gal Mishne, and Stefan Steinerberger. Randomized near-neighbor graphs, giant components and applications in data science. Journal of applied probability, 57 2:458-478 2020.
Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, Abir De, and Rishabh K. Iyer. Grad-match: Gradient matching based data subset selection for efficient deep model training. In Proceedings of the International Conference on Machine Learning, 2021.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei Rusu, Kieran Milan, John Quan, Tiago Ramalho. Agnieszka Grabska- Barwinska, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114
(13):3521-3526, 2017.
Alex Krizhevsky, Learning multiple layers of features from tiny images. Technical Report TR-2009, University of Toronto, 2009.
Alex Kulesza and Ben Taskar. k-dpps: Fixed-size determinantal point processes. In Proceedings of the International Conference on Machine Learning, pp. 1193-1200, 2011.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11))2278-233) 1998.
Jure Leskovec and Christos Faloutsos. Sampling from large graphs. Proceedings of the ACM
SIGKDD international conference on Knowledge discovery and data mining, pp. 631-636, 2006.
Angsheng Li and Yicheng Pan. Structural information and dynamical complexity of networks. IEEE Transactions on Information Theory, 62(6))3290 2016.
Xin Li and Yuhong Guo. Adaptive active learning for image classification. Proceedings of the IEEE conference computer vision and pattern recognition, pp. 859-866 2013.
Mengchen Liu, Jiaxin Shi, Kelei Cao, Jun Zhu, and Shixia Liu. Analyzing the training processes of deep generative models, IEEE transactions on visualization and computer graphics, 24(1):77-87, 2018.
12

---

Published as a conference paper at ICLR 2025
Shixia Liu, Weikai Yang. Junpeng Wang, and Jun Yuan. Visualization for Artificial Intelligence. Synthesis Lectures on Visualization. Springer Cham, 2025.
Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott Reed, Cheng- Yang Fu, and Alexander Berg. Ssd: Single shot multibox detector. In Proceedings of European Conference on Computer Vision. pp. 21-37, 2016.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A robustly optimized bert pretraining approach. CoRR, abss/190..10/ 11692, 2019.
David Lopez-Pazz Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in neural information processing systems, 30, 2017.
Pan Lu, Liang Qiu, Jiaqi Chen, Tony Xia, Yizhou Zhao, Wei Zhang, Zhou Yu, Xiaodan Liang, and Song-Chun Zhu. Iconqa: new benchmark for abstract diagram understanding and visual language reasoning. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, 2021.
Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the Anmual Meeting of the Association for Computational Linguistics, pp. 142-150, 2011.
Adyasha Maharana, Prateek Yadav, and Mohit Bansal. D22 pruning: Message passing for balancing diversity and difficulty in data pruning. In Proceedings of the International Conference Learning Representations, 2024.
Minesh Mathew, Dimosthenis Karatzas, and C.V. Jawahar. VQA:QA: A dataset for vqa document images. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 2200-2209 2209, January 2021.
Minesh Mathew, Viraj Bagal, Rubèn Tito, Dimosthenis Karatzas, Ernest Valveny, and CV Jawahar. Infographievqa. In Proceedings of the IEEE/CVF Winter Conference Applications of Computer Vision, pp. 1697-1706, 2022.
Baharan Mirzasoleiman, Jeff A. Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In Proceedings of the International conference on machine learning. 2019.
Yixin Nie, Adina Williams, Emily Dinan, Mohit Bansal, Jason Weston, and Douwe Kiela. Adversarial nli: A new benchmark for natural language understanding. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, pp. 4885-4901. 2020.
Feng Pan, Wei Wang, Anthony KH Tung, and Jiong Yang. Finding representative from massive data. In IEEE International Conference on Data Mining, 2005.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning data diet: Finding important examples early in training. In Proceedings of Advances Neural Information Processing Systems, pp-
2021.
Geoff Pleiss, Tianyi Zhang, Ethan Elenberg, and Kilian Q Weinberger. Identifying mislabeled data using the under the margin ranking. In Proceedings of Advances in Neural Information Processing Systems, pp. 17044-17056, 2020.
Ziheng Qin, K. Wang, Zangwei Zheng, Jianyang Gu, Xiang Peng, Daquan Zhou, and Yang You. Infobatch: Lossless training speed up by unbiased dynamic data pruning. In Proceedings of the International Conference Learning Representations, 2023.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In Proceedings of the International Conference Machine Learning, pp. 8748-8766 2021.
13

---

Published as a conference paper at ICLR 2025
Sylvestre-Alvis Rebuffi, Alexander Kolesnikov, Georg Sperl, Christoph H Lampert, al. Incre- mental classifier and representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5533-55422 2017.
Nils Reimers and Iryna Gurevych. Sentence-BERT: Sentence embeddings using siamese BERT- networks. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pp. 3980-3990, 2019.
Tanik Saikh, Tirthankar Ghosal, Amish Mittal, Asif Ekbal, and Pushpak Bhattacharyya. Scienceqa: novel resource for question answering on scholarly articles. International Journal on Digital Libruries, 23(3):289-300 -011 2022.
Dustin Schwenk, Apoorv Khandelwal, Christopher Clark, Kenneth Marino, and Roozbeh Mottaghi. A-okvqa: A benchmark for visual question answering using world knowledge. In Proceedings of European Conference on Computer Vision, pp. 146-162, 2022.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In Proceedings of the International Conference on Learning Representations, 2018.
Burr Settles. Active learning literature survey. Technical Report 1648, University of Wisconsin- Madison, 2009.
Lloyd S. Shapley. Notes the n-person game-ii: -i: The value of an n-person game. Technical Report RMM6700 RAND Corporation, 1951.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Proceedings of the International Conference Learning Representations, 2015.
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. In Proceedings of Advances in Neural Information Processing Systems, pp. 19523-19536, 2022.
Swabha Swayamdipta, Roy Schwartz, Nicholas Lourie, Yizhong Wang, Hannaneh Hajishirzi, Noah Smith, and Yejin Choi. Dataset cartography: Mapping and diagnosing datasets with training dy- namics. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pp. 9275-9293, 2020.
Michalis K Titsias, Jonathan Schwarz, Alexander G de G Matthews, Razvan Pascanu, and Yee Whye Teh. Functional regularisation for continual learning with gaussian processes. In International Conference Learning Representations, 2020.
Rishabh Tiwari, Krishnateja Killamsetty, Rishabh Iyer, and Pradeep Shenoy. Ger: Gradient coreset based replay buffer selection for continual learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 99-108, 2022.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J Gordon. An empirical study of example forgetting during deep neural network learning. In Proceedings of the International Conference on Learning Representations, 2019.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 986):2579 2605. 2008.
Liyuan Wang, Xingxing Zhang, Hang Su, and Jun Zhu. comprehensive survey of continual learning: theory, method and application. IEEE Transactions on Puttern Analysis and Machine Intelligence, 46(8):5362-535 5383, 2024.
Lai Wei, Zihao Jiang, Weiran Huang, and Lichao Sun. InstructionGPTT-4: 200-instruction paradigm for fine-tuning miniGPT-4. CoRR, abs/2308. 12067, 2023.
Eyal Winter. Chapter 53 The shapley value, pp. 2025-2054. Elsevier, 2002.
Xiaobo Xia, Jiale Liu, Jun Yu, Xu Shen, Bo Han, and Tongliang Liu. Moderate coreset: A univer- sal method of data selection for real-world data-efficient deep learning. In Proceedings of the International Conference Learning Representations, 2023.
14

---

Published as a conference paper at ICLR 2025
Shouxing Xiang, Xi Ye, Jiazhi Xia, Jing Wu, Yang Chen, and Shixia Liu. Interactive correction of mislabeled training data. In Proceedings of IEEE Conference on Visual Analytics Science and Technology, pp. 57-68, 2019.
Zhao Xu, Kai Yu, Volker Tresp, Xiaowei Xu, and Jizhi Wang. Representative sampling for text classification using support vector machines. In Proceedings of Advances in Information Retrieval, pp. 393 407, 2003.
Weikai Yang, Mengehen Liu, Zheng Wang, and Shixia Liu. Foundation models meet visualizations: Challenges and opportunities. Compulational Visual Media, 10(3):399-424, 2024.
Jun Yuan, Shouxing Xiang, Jiazhi Xia, Lingyun Yu, and Shixia Liu. Evaluation of sampling methods for scatterplots. IEEE Transactions on Visualization and Computer Graphics, 270)):120 2021.
Friedemann Zenke, Ben Poole, and Surya Ganguli. Continual learning through synaptic intelligence. In Proceedings of the International Conference on Machine Learning, pp. 3987-3995, 2017.
Jianpeng Zhang, Hongchang Chen, Dingjiu Yu, Yulong Pei, and Yingjun Deng. Cluster-preserving sampling algorithm for large-scale graphs. Science China Information Sciences, 66(1); 12103, 2023.
Shichao Zhang. Jiaye Li, Wenzhen Zhang, and Yongsong Qin. Hyper-class representation of data. Neurocomputing, 503:200-218, 2022.
Y. Zhao, H. Jiang, Q Chen, Y. Qin, H. Xie, Y. Wu, S. Liu, Z. Zhou, J. Xia, and F. Zhou. Preserving minority structures in graph sampling. IEEE Transactions on Visualization and Computer Graphics, 27(2):1698-111 1708, 2021.
Haizhong Zheng, Rui Liu, Fan Lai, and Atul Prakash. Coverage-centric coreset selection for high pruning rates. Proceedings of the International Conference on Learning Representations, 2022.
Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. In Proceedings of Advances in Neural Information Processing Systems, volume 19, 2006.
Deyao Zhu, Jun Chen, Xiaoqian Shen, Xiang Li, and Mohamed Elhoseiny, MiniGPT-4; Enhancing vision-language understanding with advanced large language models. In Proceedings of the International Conference Learning Representations, 2024.
He Zhu, Chong Zhang, Junjie Huang, Junran Wu, and Ke Xu. Hitin: Hierarchy- tree isomor- phism network for hierarchical text classification. Proceedings of the Annual Meeting of the Association for Computational Linguistics, pp. 7809-7821 2023.
15

---

Published as a conference paper at ICLR 2025
A COMPARISON OF ENCODING TREE CONSTRUCTION METHODS
The construction of the encoding
an important step in our method. To the best our knowledge. there are two methods for constructing the encoding trec: the one proposed by Li & Pan (216) and the one proposed by Zhu al. (023). Both methods adopt the variations of the Huffman tree to construct the encoding tree. The key difference is that /huu et al. (2023) further compresses the tree to certain height to improve efficiency in subsequent processing. We assess the two methods by calculating the Pearson correlation of the resulting node-level structural entropy. As shown in Table 5 the correlations on CIFARIO, CIFAR 100, and ImageNet- 1K exceed 0.99. Therefore, the choice of the construction method has negligible effect on the sample selection results. In this paper, employ the more recent method proposed by Zhu et al. (2023).
Table 5: Pearson correlation of the node-level structural entropy obtained from the two methods on CIFAR1O, CIFARI00, and ImageNet-IK.
CIAFRIO
CIFARI00
ImageNet-IK
Correlation
0.996
0.999
0.992
B PROOF OF PROPOSITION
We first present two lemmas essential for the proof of Proposition
Lemma 1. Let = (V, E, W) be an undirected, weighted graph and T be its encoding tree. Then the struciural entropy H(G,T) T) can be writlen as:
H(G, T) vol(V)
1
Σ
Wa,r log vol
Σ d(u) log
(a,0)EE
wEV
where Way is the weight of edge (u, u is the least common ancestor of node and in T, and d(uu) is the weighted degree of node u.
Proof of Lemma 1. According to Eq.
derive that:
H(G,T) - Σ g(a) log vol(a)
(V) vol(a-)
aeT
1
Σ aET
g(a) log val(a)
vV)
vol(a-)
(o(a)) log vol g(ax log vol(a:).
(V)
For a node a with children, the contribution of each child 3; to the summation ((,)) log col(a) g(3.) log (3,). The term g(3,) log (a) can be combined into -g(a) log vol(a) due to the shared log (ax) factor. By combining the terms with shared log vol(-) factors, Eq. 7 can be rewritten as:
(G,T) vol(V) is non-teaf (Echildren(())
Σ
Σ
s(8)) -s()) log vol(a)
Σ g(a) log vol()))) leaf
Note that Σ #cchildrea())) ((B) g(a) represents the difference between the total weight of outer edges of a's children and the total weight outer edges of a. This difference precisely twice the total weights of edges between the communities represented by a's children. Furthermore, each edge
16

---

Published as a conference paper at ICLR 2025
(u, u) in the graph contributes only to the node V Therefore, transform the first term
into a sum over edges in the graph, yielding:
g(a) log vol(a) )
=(G,T)= vol(V)
2 Σ
Wu, log vol V o)
Σ leaf
(9)
(u,r)EB
The set of leaf nodes in the encoding tree corresponds the of nodes in the graph. Additionally, for a leaf node a and its correpsonding graph node u, we have g(a) = vol(a) d(u). We can conclude that:
H(G,T) = (Vl
Σ
Why log col V Vo) u) - Σ d(u) log d(o)
(10)
(u,))E
uEV
which proves the lemma.
Lemma Winter 2002). Eq.
2 is equivalent to:
((u)
(H(G(V>,u U (u)),T) H(G(V=.)::))
(11)
V xEll
where II the set of all permutations of nodes in V, and v, denotes the set of nodes preceding in permutation
Based on the two lemmas, we develop a proof of Proposition
7 For brevity, denote the subgraph and G(V by GR,u- (Va, Ex.u, W'). Lemma gives:
Proof of Proposition!
by G (V+t E W)
H(G n.u T) vol(V) (2
Σ
Wz,y log vol(x Va)
Σ
d(z))ogd(<))
(12)
(x.
zEV
and
H(Gm, T) vol(V) (2
Σ
Wx.y log vol( V V)
Σ
d(x) log
(13)
(F.
NEV..M
Then
H(G
k,u T) HHGGR. T)
2( Σ
Wxyy log co Vv)
Way log vol (2 y))
vol(V)
(L.
(n,w)E
(14)
Σ
log(z)
Σ ZEV...
d(x) d(z)))
.VV
Note that V++ V..u u {u) and D E u U((,,) 1 ((() Vr,ud, where N(u)) is the set of neighbors of u in G. Therefore,
H(G+ T,u: T) H(Gx T) vol(V)
Σ
Wao log vol(u - d(u) log d(w) (15)
DEA(w))V....
17

---

Published as a conference paper at ICLR 2025
We rewrite (wEN( log vo indicator function. Then, the Shapley value in Eq. 11 can be rewritten
V e) [veN(u) Ie Va,ul log vol V v), where is the
(uu) = |V!
H(G U fu)l. -H(GGVV,))))
men
Σ 1/u E V V log vol(u V d(u) log logd(u))
2
V
vol(V)
mEll
vEN(u)
(16)
2
Σ
Tl Va Win log vol(u Vo) vol(V) (uu) () log d((u)
TEll (E)
2
Σ
Whe log rol(u V v) xEIl
Ile Va,al
1 vol d(u) log d(u).
VV]
(EV(u)
Note that Enen He E Va,ul is Mi!! 2
since there are 2
!V!
permutations where v precedes u. Thus, we
have:
6(u) vVl(V) E
Wh. log vol(u Vv) vol ) d(u) log d(u)
vEN(u)
Σ (EN(u)
Wupe log vol((rvv)) - d(u) log d(u)
vVl
(17)
Σ (B.
Wa,v log vol(awve) d(u) log d(u)
vVl
which proves the proposition.
C THEORETICAL ANALYSIS OF NODE-LEVEL STRUCTURAL ENTROPY
C.1 NODE-LEVEL STRUCTURAL ENTROPY AND SAMPLE COVERAGE
In this section, we prove that node-level structural entropy serves as a lower bound for the sample coverage. Following previous work (Zheng al. 2022), we assume that the dataset {x, y1 contains i..dd samples drawn from an underlying distribution PN. with probability measure μ. We discuss a certain sample u's ability to cover the entire distribution, i.e., how well the sample can cover the entire distribution. The sample coverage of sample u can be quantified by the coverage of the entire distribution by a ball B(u, r) centered at u with radius r (Zheng et al. 2022
P(u,r)
(B((.)) du(x).
When is fixed, the larger P(u, r) is, the better sample covers the distribution. Directly calculating P(u, r) is difficult because we do not know the underlying distribution P,,. We next prove that node-level structural entropy serves
lower bound for the sample coverage.
We assume that the edge weights are the range [L, R). where > L
Consider a node
connected to I other nodes (u1, 02, ....... ux) with edge weights (W1, W2,..., w.). In the BFS tree rooted at u, let the total vol of the subtrees of U1, o2..., 2% be vol,, volz, volg. From the follows: vol(u) is initially
perspective of u, the calculation of S.(u) connected to u, add vol, of o; to vol(u), and then add ww) to Se(u). If the nodes are connected in the oreder [T], ......, } the results is:
0; For each node u;
k
S.(u) = Σ Wx. log(vol,, + voln, + ...oo....)
18

---

Published as a conference paper at ICLR 2025
In practice, the nodes are connected in specific order minimize (u). Consequently, S. (u) less than or equal to values obtained in any other order. Consider the order in which nodes are connected from the smallest w; to the largest w/. We derive that:
(u)
War log(uol
vol x..
Wme
Wi
log
(vola, +... volTx)
(Jensen's 's Incquality)
Σ/=1 wi
1=1
Wi
log
(volm (Wxs, + Waz + t..e)xe)! )
Σ w
(18)
< kR log
(uolx) (Wir
Wxz ...WT.) ) Σ ws)
S &RRlogg log Σ (kvolze Wax/ Σ w.
Because volag [kLMM & &R where nry is the number of nodes in the subtree of Un,. So we
have:
Sa(u) < kRlog(k 2
nu, Woy me
Assume that all nodes in the subtree of 0; are B(v,, Then we have:
E Emmay]
du n nP((,r)))
B(m
which can then lead to:
[[)](u)] & EobRlog R
nhe Wn:!
ws)
i=1
k
k
< Rog E 2
Σ
nr Wms
Σ
(Jensen's 's Inequality)
(19)
xm1
kR E nk R
Σ P(ume
Wum!
Σ wi
Since
Σ Plune Wwi!
Σ w; p(urr)
actually the Nadaraya-Watson estimator of P(u,r*) have:
E[S.(w) < KRlog IE
nk* nk²
Thus, the following theorem is obtained:
Theorem 1. For > r², (u) ensures an lower-bound of the Nadaraya-Watson Watson estimator P(u,, r*) of P(u,r") with inequality:
KK (IS.,)))))) S [(
RK2R exp
where r" is constant related to the distribution P, and the location of u in the metric space. Theorem shows the correlation between (u) and P(u, r). For a certain sample u, a larger S, (.(u)
guarantees stronger sample coverage.
19

---

Published as a conference paper at ICLR 2025
We further conduct an empirical validation to demonstrate that nkan exp( 1 Su()) provides relatively tight lower bound for P(u,r), r). To precisely calculate P(u,7), we simulate the data using a Gaussian Mixture Model, where the class centers pi...., PC drawn from a standard Gaussian distribution (0, 7). data with sal-world scales by generating 10 classes with 5,000 samples each, matching the statistics of CIFARIO I0. Our results show that: 1) For 90% of the samples, P(u, r)/ n exp( ER (u)) lies between 1.00 and 1.45; 2) For 99% of the samples, P(u, r)/ R exp( SR (u))) is less than 1.97. These findings support the theorem that maximizing Se (u) during selection improves sample coverage.
For each class c, the samples are drawn from (uu,, 7). We align the synthetic
(
C.2 SAMPLE COVERAGE AND MODEL PERFORMANCE
2022) has demonstrated that a better distribution coverage brings a lower empirical loss, as depicted by the following theorem:
Previous work (Zeng et al.
Theorem 2. Zheng et al. (022) Given i..dd. samples drawn from P.. as S = (mx, Vi Ji(n) where 2; E X Re is the feature representation of example i and ys E [C] is the class label for example i, a coreset S' which is a p-partial r-cover for Pp on the feature space X, and an e > 1 if the loss function U(, y, w) is x -Lipschitz continuous for all y, w and bounded by L,, the class-specific regression function no (1) = ply = c/ar) is -Ip-schchit for all c, and 1(,, y, hir) = 0, v(r, y) E S¹,
then with probability at least 1
log ptc-1
Σ JESES
1(x, yi hs:) + LV
(20)
VL
2n
Theorem 2 suggests that better sample coverage results in a tighter bound on the empirical loss for the entire set. Given the relationship between Su(u) and sample coverage, selecting samples with high node-level structural entropy effectively enhances model performance.
D DATASET STATISTICS AND DETAILED EXPERIMENTAL SETTING
D.1 SUPERVISED LEARNING
Image classification. The CIFARIO and CIFAR100 datasets each consist of 50, 000 images of 32x32 pixels for the training set, with an additional 10, 000 images for testing. CIFAR1O includes 10 distinct classes, while CIFAR100 includes 100 classes. The ImageNet- K dataset includes 1, 28, 167 images across 1, 000 real-world classes for training, along with 50, 000 images for validation. Following common practice Maharana et al., 2024), we trained ResNet-18 for 200 epochs on CIFAR 10 and CIFAR 100, and ResNet-34 for 60 epochs on ImageNet-IKK The batch size is set to 64. We use an SGD optimizer with 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 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 -nd-model-in------ -nt---otttooopp 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. 2024), we fine-tune the RoBERTa model for 10, 000 iterations with batch size of 16. We use the SGD optimizer with an initial learning rate of 0. 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 the training and test splits, with each review labeled by sentiment (positive/negative.. Following previous work (Maharana et al.) 2024), 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
20

---

Published as a conference paper at ICLR 2025
SSD (iuu et al. 2016) with VGG-16 (Simonyan & Zisserman 2015) backbone from scratch for 80 epochs with 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 linear warm-up strategy for the first 8 epochs and is then reduced by 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) Mini-GPT4 (Zhu et al. 2024). The visual question answering datasets used for validation reasoning, visual reasoning, knowledge retention, and abstract understanding. We use the same setting as the second-stage stage fine-tur tine-tuning for Mini-GPT4 (Zhu et al. 2024). 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 0.05. We use a cosine annealing scheduler with minimum learning rate of 0.00001.
the model's abilities in various aspects, including logical
D.2 ACTIVE LEARNING
We use the same setting as training on ImageNet-Ike IK in Appendix D.I
D.3 CONTINUAL LEARNING
For continual learning, we follow Borsos et al. (2020) for experiments on Permuted MNIST, Split MNIST, and Split CIFARIO, and follow Hao et (2024) for experiments on Split CIFAR 100 and Split Tiny-ImageNet. We use increasingly complex models as dataset complexity grows: a two-layer MLP for Permuted MNIST, four-layer CNN for Split MNIST, ResNet-18 for Split CIFAR and ResNet-18 with multi-head output (Zenke et al. 2017) for Split CIFAR100 and Split Lny-lmageNeet. For each task, we first randomly select M samples from all available samples. Then, we train the model on these samples for E epochs with batch size of B. During each training iteration, all replay samples are used with a weight of A. The initial learning rate is set to ir, for the first task and decays by factor of 17 for each task. All hyperparameters, except X, are fixed for all baselines and our method. The value of À is determined through a grid search over {0.01, 0.1, 1, 10, 100, 1000). Table 6 shows the fixed hyperparameters for different datasets. Table 7 shows the optimal À for all baselines and our method.
E SELECTION HYPERPARAMETER SETTINGS
E.1 SELECTION HYPERPARAMETER
We conduct grid search to optimize three hyperparameters: the number of neighbors l for construct- ing the ANN graph, the cutoff ratio 3 to remove the most difficult samples, and the imbalance factor to maintain the balance between different classes.
Selecting an appropriate value of i: is erucial it can significantly affect the quality of the sample graph and thus affect the selection result. If is too small, the graph becomes too sparse, making the selection sensitive noise and outliers. If k too large, the graph will be 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 balance to preserve meaningful structures without introducing noise or irrelevant information.
Table 6: Training hyperparameters for continual learning.
Permuted MNIST
Split MNIST
Split CIFAR10
Split CIFAR 100
Split
Hyperparameters
Tiny-ImageNet
M
1000
1000
1000
2500
5000
Optimizer
Adam
Adam
Adam
SGD
SGD
E
400
400
400
B
256
256
256
Ir:
0.0005
0.0005
0.0005
0.15
0.20
1
1
0.875
0.875
21

---

Published as a conference paper at ICLR 2025
Inspired by Zheng al. (2022), also search the hard cutoff ratio 3 that removes 3 of the most difficult samples because they are usually outliers and contain noisy samples in the dataset. In addition, also allow negative 3 during the grid search, which indicates that will remove [3] of the easiest samples to focus on difficult samples, which has been adopted by [Sorscher et al. (002).
Maintaining 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.) 2022) 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 y > which allows for the selection of up n 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.
E.2 PRELIMINARY EXPERIMENTS ON
As k decides the sample graph and the range of possible k is large, we conduct preliminary experi- ments on CI CIFART00, and ImageNet- to determine a candidate range where the structure of the sample graph is effectively preserved by the ANN-graph.
Spectral clustering is an effective method for revealing the underlying structural features 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 ENN-graphe Based on the spectral clustering results, we measure the structure preservation of the ANN- 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 metries assess the quality of clustering by evaluating the compactness and separation of clusters. We use the Silhouette Score and the Davis-Bouldis Index as the internal metrics.
Directly applying spectral clustering to large-scale datasets is unsuitable due its high complexity of O(n"), ). where n is the number of samples in the dataset. To address this, we use growing neural gas Fritzke 1995) to generate a reduced graph with fewer nodes. The key feature of this method is the preservation of the topology of the kNN-graph. Specifically, this method generates neurons representing the sample distribution of the kNN-graph. Then, it integrates the edges in the -NN-hr into the neuron connections, resulting in sparse, clustering to this reduced graph to accelerate the evaluation of the choice of k.
graph. We apply spectral
In the preliminary experiments, we test k in 21, 100} CIFAR1O, CIFAR100, and ImageNet- IK. Fig. 4 presents the results. As the value of & 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
Table 7: Optimal replay sample weight À in continual learning.
Permuted MNIST
Split MNIST
Split CIFARIO
Split CIFARI00
Split
Dataset
Tiny-ImageNe
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
D 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.01
0.01
0.01
0.01
AUM
0.01
0.01
100
100
10
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
0.01
0.1
0.01
0.1
22

---

Published as a conference paper at ICLR 2025
Accuracy
ACCuEsSy
Stare
Siocuette
-0.0
(a) CIFAR10
(b) C0
(c) ImageNet-1K
Figure 4: Results for the preliminary experiments on: (a) CIFARIO; (b) CIFARI00; (c) ImageNet-IK An increase in the accuracy, the Rand Index, the mutual information, and the Silhouette Score, as well as a decrease the Davis-Bouldin Index, indicates better structure preservation.
Table 8: Optimal hyperparameters of our method supervised learning and active learning. The three numbers in each tuple refer the number of neighbors k the cutoff ratio B, and the imbalance factor y, respectively.
Sampling rate
CIFARIO
CIFARI00
ImageNet-1K
ANLI
IMDB Review
PASCAL VOC
VQA
(active learning)
ImageNet- IK
1%
(17.0.75,1.05)
(14,0.85.113)
(20.0.9.1.3)
(15.0.35
(10.0.7.12)
(15.0.7.)
(10.0.15.)
(25.0.25.1.05)
(14007.1.1)
(10.085,1.1
(250.75.1.2)
(15.0.3.1.05)
(18.085,11))
(15.0.7/)
(10,011))
(25.0.2.1
5%
(19.0661.05)
(21.0.8.1.)
(25.0.65.12)
(.5.0.25.1055)
(10.0.5.1.0)
(15.0.5))
(10,0.1.)
(25.0.4.1.35)
10%
(11,0:35,1.))
(19.06,111)
(25.041115)
(15.0.31.15)
(19,04,1140
(15.0.35/)
(10,0115))
(25,0.45,
(13.0.2,10)
(15.0.45.1115))
(25.0.3.1.1)
(1500.1.05)
(18.0.3,1.1)
(15.0.1,)
(10.0118))
(25,0.35.1.15)
(15,0.15.1.0)
(15.0.1,110)
(20,0.5.1.05)
(15,0.0.11)
(10.0.05.1005)
(15.0.15/)
(10,0.17)
(25.0.0.1.I)
70%
(24m001.8)
(18.0.1,140)
(20,0.01.0) m))
(15.0..122)
(10,0.0,1
(15.0.05/)
(10,00.0)
(25.0.01.115)
stabilize around log, n, where is the number of samples in the dataset. Thus, we focus our grid search for & values near log, n.
E.3 GRID SEARCH RESULTS
0.95, 1} and 7 in For all experiments, we search 3 in -0.95..5,... -0.05, 0, 0,.00...........888
{1, 1.05,.... 1.5). For CIFARIO and CIFAR 100, search À in {10, 11. ......... 30). For ImageNet- IK, we search it only in {20, 25} due to computational costs. To save computational costs, we set k to around log, for experiments on other datasets. With this choice. the ANN graph has O(n log, n) edges, resulting in Shapley value calculation time complexity of O log, n). This complexity is comparable to sorting and is lower than equal that of typical sample selection methods, which at least (n log, n.) when sorting is required and O(n?) when an enumeration of all pairs of samples required. For extremely large datasets (e.g. DataComp (Gadre et al. (024) with billions samples) where this complexity becomes impractical, potential solution to split the dataset into bins before selection. Determining an optimal splitting method remains an open question and a promising direction for future research. We evaluate every possible combination of the hyperparameters. Table presents the optimal hyperparameters for supervised learning and active learning. Table presents the optimal hyperparameters for continual learning.
23

---

Published as a conference paper at ICLR 2025
Table Optimal hyperparameters of our method in continual learning. The three numbers in each tuple refer to the number of neighbors k the cutoff ratio B, and the imbalance factor y, respectively.
Permuted MNNST
Split MNIST
Split CIFAR 10
Split CIFAR100
Split Imag-em
Memory size
100
(15.-0.15,1.255) (15,00451155)
(15.0.7.1.5) (15,0.75.1.1)
(15,-0.95.10) (15,-0.35.L0) (15,-0.,1.11
(15,-0.15.10)
200
(15,-088,1.0)
(15,-09,1.0)
F DETAILED EXPERIMENTAL RESULTS
F.1 SUPERIVISED LEARNING
We present detailed experimental results for supervised learning from Tables to 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 gaggh-samlingg-atte settings for simple datasets, such as the 70% setting for CIFARIO, all methods perform closely to using the entire training set, leaving little room for improvement.
In low-sampling-rate settings for challenging datasets, such the 1% setting for ImageNet- 1K, the performance of all methods is limited due to the insufficient number of samples per class.
scenarios where models are fine-tuned from pretrained weights, the knowledge within these models anchors the performance at certain level, leading similar performance across all methods.
Despite these factors, method achieves significant improvement in many settings. For example, achieves a 5.52% increase in accuracy when selecting 2% of the samples from ImageNet-IK.
Table 10: Results on image classification (CIFAR10). The best one is bold, and the runner-up is underlined.
Dataset
CIFARIO (100%:95.49)
Sampling rate
70%
50%
20%
10%
5%
2%
1%
Random
94.29 4: 0.08
92.33 +: 0.15
84.17
0.62
71.95
1.50
59.88 + 2.45
45.51 + 1.68
35 14 :: 1.49
Moderate
94.04 + 0.26
92.36
+: 0.17
80.96
2.56
63.91 + 1.56
49.94 + 0.70
32.00 = 2.11
26.18 + 1.94
CCS
94.23 0.35
93.83 1
83.85
2.39 75.56
65.89
1.04
49.02
1.35
40.24 = 0.96
D2 Pruning
93.17
93.70 0.20
76.56
65.12
45.44 1.75
39.03 1.69
GraphCut
94.38 +: 0.20
92.43
81.98 0.48
69 1 0.57
59.36 + 2.43
46.93 4 2.21
39.68 + 1.15
Entropy
94.13 0.30
92.39 1: 0.40
75.31 4.32
60 6.23
46. 5.96
35.85 4 4.33
29
4.29
Forgetting
94.76
94.34
35.21
30.87 0.55
27.22 -
23.62
EI.2N
94.75 0.32
94.10
0.45
46.41 4.84
22.40 0.62
15.66 + 0.18
13.05 0.20
12.75 + 0.56
AUM
94.90 0.17
94.38 + 0.20
51.98
1.32
30.56
0.42
22.92 + 0.38
18.10 + 0.47
14.50 1.35
Variance
90.45 0.09
85,81
0.39
64.90 0.53
53.64 1.02
44.45 0.77
36.61 0.70
31466 0.92
k-means
93.87 0.33
93.19
83.65 0.94
72.66
62.68
1 1.12
18.35
2.29
38
k-DPP
93.84 0.10
0..12
84.09 1.21
74.62
0.40
61.96
4.87
46.58 + 1.76
35.16 2.92
SES (Ours)
95.01 + 0.08
94.50 = 0.05
88.31 + 0.13
24 0.72
69.82
0 84
54.78
1.36
45.25 0.81
24

---

Published as a conference paper at ICLR 2025
Table 11: Results on image classification (CIFARI00). The best one is bold, and the runner-up is underlined.
Dataset
CIFARIO0 (100% ::7.90)
Sampling rate
70%
%
20%
10%
5%
2%
1
Random
74.72 +: 0.16
70.51 +: 0.43
52.29
2.32
37.38
0.80
23.03 + 0.48
13.38 =: 0.36
8.57 +: 0.65
Moderate
74.61 0.10
69.95
0.32
49.37
0.58
30.53
1.44
17.68
0.50
9.28
0.34
5.97 0.35
CCS
76.10 0.29
73.12
+: 0.21
58.39
1.04
44.92
1.81
28.68
0.99
15.93
0.62
10.28 + 0.54
D Pruning
76.00 0.56
74.45 +: 0.36
59.08
0.53
44.78
0.78
26.68 + 0.85
13.90 = 0.66
9.61 + 0.44
GraphCut
7
65.79
1: 0.35
1.10 25.08
16.46
0.35
10.78
0.52
0.33
5.94 0.16
Entropy
76.81 0.12
62.52
33.28
7.11 21.85
13:90
4.75
8.31
5.30 1.71
Forgetting
76.64 0.13
68.75
0.34
25.17 1.12
16.45
0.37
10.70 0.49
7.82 + 0.37
5.90 + 0.09
E1.2N
76.15 0.50
66.19
0.48
14.85 0.43
7-50 + 0.27
5.28 + 0.12
3.83 + 0.07
3.17 0.14
AUM
76.84
67.81 0.59
16.66 0.90
8.54=0.11
5.60 0.18
4.35
3.56 0.10
Variance
73.69
68,42
49.60 0.28
22.70 0142
13.71 0.38
9.18
k-means
74.93 +: 0.12
72.86 1.36:0.11
56,86 0.88
42.09 0.52
26.39 + 0.73
14.92 - 0.75
8,90 $.90 0.31
k-DPP
75.34 + 0.45
73.16 0.45
1.01 56.88
42
0.41
26.55 + 0.9
14.31 + 0.33
8.23 + 0.27
SES (Ours)
77.23 +: 0.10
74.63 + 0.17 61.52 + 0.78
48.02 0.98
33.39
0.27
19.68 +: 0.51
14.16 +: 0.48
Table 12: Results on image classification (ImageNet-IK) The best one is bold, and the runner-up is underlined.
Dataset
ImageNet-IK (100 :73.63)
Sampling
70%
50%
20%
10%
5%
1%
Random
71.63 +: 0.12
69.26 +: 0.17
58.90
0.12
47.10
0.26
34.04
0.42
16.56
0.11
5.50 0.28
Moderate
71.33 + 0.04
68.72 +: 0.07
55.23 0.27
40.97
+ 0.18
25.75
0.16
11.33 + 0.31
4.52 + 0.24
CCS
70.74 0.09
69.23
+- 0.09
0.95 60.04
50.41
0.11
36.92
1.62
19.92 + 1.36
9.43 0.31
D2 Pruning
71.20 0.07
70.32
0.05
58.91
50.81
0.24
37.12
0.00
18.97 0.05
11.23 0.26
GraphCut
68.91 + 0.05
68.72 + 0.07
55.28
0.17
44.79
+ 01.6
33.54 + 0.12
20.07 0.21
11.49 + 0.12
Entropy
0.74
09.21
51.76 0.16
38
0.34
22.78 1 0.73
7.01
1.95 1.93-10 0.15
Forgetting
70.57 - 0.04
70.46
60.77 0.02
48.73
0.155
15.13 0.23
5.66 0.30
EL2N
71.68
65.98
31.90 3.64
12.57 -.11
0.36
3.25
1.90 0.09
AUM
69.94 + 0.30
65.36 0.11
21.91 0.13
10.50 0.19
6.42
0.00
2.24 0.05
Variance
70.12 0.09
66.09 0.01
35.13 0.09
13.85
0.85::000 0.02
0.05
4.02
1.81 0.06
k-means
70.33
69.47
35.51
0.08 18.67
9.65
D-PPP
70.84 + 0.09
69.85
59.92 0.33
46.10 0.33
34.41
16.33
0.15
7.49
SES (Ours)
72.80 =: 0.03
71.05
0.09
63.24 1 0.06
53.59 0.09
41.88
11.88=000 0.13
25.59
0.17
13.43 0.37
Table 13: Results text classification (ANLI). The best is bold, and the runner-up is underlined.
Dataset Sampling rate
ANLI (49.5:
50%
%
10%
2%
1%
Random
39.52
38.82
1.29
1.04
Moderate
46.84 1: 0.31
45.11 1: 0.39
41.95 1 0.33
10.16 1: 0.85
38.99 1: 01.45
35.83
1.39
33.91
1: 0.62
0.05
36.82
1 Pruning
48.56 + 1.22
47.49
1::00+000 0.17
42.77 + 0.36
41.43 + 0.24
40.34 + 0.07
37.92
1.44
36.29
+ 0.59
GraphCut
16.11 0.67
11.33
12.12
39.86
0.27
38.15 0.74
35.11 0.80
31.02
0.61
Entropy
46.32 4: 1.11
45.33
0.44
41.45 1: 0.33
39.67
0.22
38.54
0.66
36.69
0.33
36.40
0.19
Forgetting
18.73 0.35
12.29
0.17
39.82
0.16
38.37
0.60
0.33 35.95
35.78
0.12
35.03
0.77
EL2N
08.70 0.65
47.85
0.98
43.14 1.68
39.63
2.20
37.32
1.05
31.33
1.15
34.27
0..1
AUM
17.86 0.27
17.38
0.37
13.37
0.71
10.02 1.51
34.66
0.73
34.16 0.12
33.62
Variance
47.97 - 00.00
17.87 1: 0.56
10.70
0.16
38.75 0.62
33.32
0.03
33.50
0.03
33.17
0.12
k-means
46.48 1 0.24
46.52 1.06
42.42
0.72
40.37 0.65
39.89
0.10
36.74
0.29
36.11
0.40
k-DPP
47.74 0.07
47.02
0.02
43.41
0.59
10.98 0.46
40.12
0.26
37.44
0.11
36.66
0.23
SES (Ours)
49.00 0.00 0.08
48 18.22-22 0.54
45.91 0.27
43. 63 1.00
41.82 0.43
39.88 -: 0.7
38 16 0.38
25

---

Published as a conference paper at ICLR 2025
Table 14: Results text classification (IMDB). The best one is bold, and the runner-up is underlined.
Datuset
Review
Sampling rate
70%
50%
20%
10%
5%
2%
1%
Random
95.25 + 0.22
95.01
0.31
93..3
0.68
91
0.17
89 19.600
1.89
83.25 :: 1.96
73.31
1.91
Moderate
95.39 + 0.19
95.31
0.07
94.03
0.73
92.55
0.47
90.31 + 0.43
58.31 = 4.29
50.81
0.55
95.22
0.19 95.35
03.44
0.23
80.80
1.47
85.73
82.05
D Pruning
95.43 1: 0.16
95.40
0.20
93.75
0.46
92.44 0.60
90.77
0.33
57.40 0.78
80.06 0.85
GraphCut
95.39 0.15
95.21
0.29
93.37
0.57
91.69 0.66
90.33
0.31
86.85 1
82.26 0.99
Entropy
95.39 + 0.31
96.17
0.22
93.92
0.50
92.57
0.97
90.30 + 0.63
77.16 + 4.52
59.11
1.70
Forgetting
95.41 + 0.11
95.31
0.17
93.66
0.30
89.11
0.58
58.78 2:28
55.81 4.65
52.38 1
EL2N
95.29 = 0.19
96.34
0.21
91.31
01.11+00 0.19
60.29 = 0.09
19.88 1.35
47.18 3.30
43.74 0.81
AUM
95.27 + 0.66
95.23
0.16
90.60 0.13
$5.68 0:21
49.81
1.30
13.13
36.29
Vartance
05.41 0.16
95.40
0.20
93.75 0.46
92.44 0.00
90.77
+ 0.33
87 0.78
80.06 8.85
k-means
05.34
95.22
0.23
03.98
0.74
90:21 0.88
81.51
D-DPP
95.29 + 0.37
95.13
0.21
93.76 0.55
92.50
0.58
89.97
1.42
86. 14.14.22 2.53
77 3.31
SES (Ours)
95.60 0.16
95.40 0.12
94.57 0.09
92.96 0.56
91.42 0.24
88.58 0.47
83 2.05
Table 15: Results on object detection. The best one is bold, and the runner-up is underlined.
Dataset
PASCAL YOC (100% (100%%76.29)
Sampling rate
70%
50%
20%
10%
5%
2%
1%
Random
71:02 + 0.26
72.10
0.32
63.45
0.45
57.56 0.45
13.17 - 0.67
18.78
0.21
9.24 0.96
Moderate
73.42
72.03
0.57
5.13
OCS
71.61 + 0.15
72.27
= 0.23
63.72 1 0.59
57.85
1:55:000 0.63
39.01 + 0.81
17.26
- 0.62
8.19 1919:11 0.57
D Pruning
74.46
72.55
0.23
GraphCut
67.45 + 0.35
64.15
+ 0.54
53.12
0..30
38.29
+-1.2
26.81 + 0.32
8.56
0.64
8.16 4 0.54
AL-MDN
74.51
70.36
k-means
74.22 + 0.31
72.35
0.19
65.52
+-0.8
57.01
0.49
43.35
0.60
16.96 + 0.78
5.16 0.89
k-DPP
0.53
SES (Ours)
75.20
0.29
73.33 0.33
66.52 0.41
59.52 0.14
45.92 0.46
23.39 0 0.22
16. 0.62
Table 16: Results visual question answering. The best one is bold, and the runner-up is underlined.
Dataset
CC SBU Align (1:0.44)))))))
Sampling rate
70%
50%
20%
10%
5%
Random
29.66
0.15
0.05
0.26
29 0.14
28.20
25.51
1=.00.0 0.46
25.11
Moderate
29.96
0.14
29.67
+: 0.13
29.53
0.22
29.11
0.23
27.30
0.25
24.85
0.36
26.64 - 0.41
CCS
29.93
0.06
29.90
0.05
29.94
0.16
29.91
0.25
27.71
0.37
25.31
0.37
25.50
0.41
D Pruning
30.09 1: 0.13
29.97
1 0.19
29.44
0.22
29 0.27
26.44
1: 0.23
25.03
0.30
26.29 0.37
GraphCut
0.41
26.51
Instruction
30.12 0.15
29.03
0.25
29.82.40.22 0.27
0.28 29.01
0.42 26.76
0.49 23.72
24.00 0.46
k-means
09.11
0.35
D-DPP
29.33 + 0.15
29.55 + 0.12
29.48 + 0.08
29.27 0.12
0.34 28.
25.93
0.46
26. 13 0.34
SES
F.2 ACTIVE LEARNING
We present detailed experimental results for active learning in Table 17 Our method consistently performs better than baselines across all sampling rates.
Table 17: Results for active learning. The best one is bold, and the runner-up is underlined.
Dataset
ImageNet-IK (100 :73.63)))))
Sampling rate
70%
50%
20%
10%
1%
Random
71.12 1: 0.25
69.43
0.04
58.77
0.335
47.36 17:36-100 0.20
31.41
0.15
16.41
0.40
5.41 1: 0.23
Moderate
71.48 0.05
68.68
0.06
56.35
0.01
12.29
26.77
0.01
11.37
0.22
4.22 0.17
CCS
0.116
69.50
0.07
58.85
1.16
45.06.103
28.02 0.17
9.03
1 0.400
233 1 0.18
GraphCut
71.50
0.21
69.16
0.09
56.08
0.24
10.99
21.30 0.17
7.90
2.16 0.08
D Pruning
71.62
0.11
69.02
0.21
59.65
0.111
45.97 100T1100 0.32
28.08
0.37
14.24
14.24
4.79 - 0.31
Protolypicality
70.12 4 0.04
0.08 66.00
49.20
0.09
0.04 35.27
24.14 0.15
0.08 13.88
4.95 4 0.05
SES (Ours)
72.11 0.07
48.10
F.3 CONTINUAL LEARNING
In addition to baselines from Sec. 5.1 we include nine widely used baseline selection methods
for continual learning: 1) k-ccentrr (Sener & Savarese 2018), which iteratively selects samples
26

---

Published as a conference paper at ICLR 2025
that are least similar those already selected, 2) Gradient matching (Campbell & Broderick] 2019), which selects samples whose average gradient closely approximates the average gradient of all samples, 3) FRCL (Titsias et al. 2020), which optimizes subset of samples to minimize the posterior uncertainty of the Gaussian process induced from the embedding representations, 4) iCaRL (Rebuffi et al. (017) that selects samples whose average emhedding closely approximates the average embedding of all samples, 5) Greedy Coreset (Borsos et al. (2220) 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, 6) BCSR (Hao et al., (024) 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. 7) DER++ (Buzzega et al.. 2020) that employs reservoir sampling to select samples from the input data stream, and leverages both model logits and ground-truth labels to mitigate the impact of distribution shifts, 8) GSS (Aljundi et al., 2019) that selects samples with diverse parameter gradients to ensure that the model's performance on previously learned tasks does not degrade, and 9) GCR (Twaari et al., (2022) that selects and weights samples to minimize the discrepancy between their replay loss gradients and those of the entire dataset.
In addition to the aforementioned memory construction methods, there are methods that optimize the usage of the replay memory. For example, GEM (Lopez-Paz & Ranzato 2017) prevents an increase in the loss on previous tasks by projecting the gradient updates onto subspace that satisfies the non-increasing loss constraint. These methods, when combined with memory construction methods, effectively utilize replay memory to mitigate catastrophic forgetting of previously learned tasks. However, our focus is primarily on memory construction, so these methods are not included in our experimental scope.
We conduct the experiments under three settings: class-incremental, task-incremental, and task-free. The class- itussinncremenal setting introduced in Sec. 553.1] The iuskeincremental setting is similar to the class- incremeaalt setting, except that the model is aware of the task of each sample during testing. This specificity allows the model to select labels appropriate for the given task rather than from a pool of all tasks. The task-free setting is designed to simulate continuous shifts in data distribution, where task boundaries are not known during model training. Consequently, the replay memory is updated after each data batch rather than after each task. Specifically, we employ the merge-reduce method for memory updates, as proposed by Borsos et al. (2020). This method divides the memory into equally sized slots, and for each new data batch, representative samples are selected to fill a slot. If all slots are full, two slots that represent the same number of original samples are merged. This is done by selecting representative samples from both slots form single updated slot, which then represents the combined samples of the original two. In our implementation, the memory is divided into 10 slots for all memory sizes.
We present detailed experimental results for continual learning in Tables 18 method consistently performs better than baselines across all settings, datasets, and memory sizes.
19 20 and 21 Our
Table 18: Results for continual learning on Permuted MNIST and Split MNIST. The best one is bold, and the runner-up is underlined.
Permuneed MINIST
Split MINIT
Dataset
Memory size
50
100
200
400
50
100
200
400
Random
75:00
77.43 0.41
79.00
0.44
81.32
922.66
1.46
96.79
97.16
Muderate
78.29
0.52
0.50
CCS
74.25
0.75
75.48
76.53
0.53
81.63
80062
1.01
80.50
0.922
94.92 0.71
98.34 1: 0.17
D Pruming
27.19 + 0.46
78.25
0.30
70:04+
+ 0.36
80.03
0.12
93.992
0.22
96.79
+ 0.12
97.69
6.88
98.07 + 0.06
GruphCol
73.31 1 0.42
76.08
6.74
78.61
1 0.56
60.59
0.29
85.57
0.37
91.34
1 1.00
94.25
0.71
98. 1 0.20
Entropy
70.74 0.35
75.64
0.30
78. 18
0.64
82,08
0.19
94.33
0.34
91.54
2 0.73
96.16 2: 01.26
1N.27 = 0.13
Forgetting
74.38
75.30
0.25
0..00
79.13
0.70
89.00
2.00
92.14 1: 0.43
96.37
98.25 0.18
E1.2N
76.57
0.24
0.20
80.34
83.56
1.01
89.54
73.96
75.54
77.47
0.55
70.90
82.51
96.36
Variance
74.33 0.47
75.67
0.38
77.42
0.32
78.70
0.34
$4.08
91.90 + 0.72
94.96
0.88
97 0.38
k-center
75.64 L 0.40
78.17
0.23
79.75
0.17
80.94
0.38
90.41
1.23
94.39 1. 0.41
96.61 1: 0.66
97.80 T1 0.13
Grudient Matching
75.73 1 0.57
71.30
0.08
79.27 1 0.58
60.71
0.50
91.55
1.06
96.39
1 0.93
97.54
0.25
98.30 1 0.26
FRCE
75.76 2: 01.45
7T.38
0.26
79.21
4 0.53
SIL88
0.30
88. 65
0.61
941.05
2 0.50
97.10
11.31
98.33
= 0.20
ICaRI.
77.01 + 0.19
78.84 + 0.46
50.65 + 0.56
81.94
0.14
02.00
1.23
80.50
+
07 8.14
98 + 0.05
Greedy Coreset
0.67
0.11
7T.74
05.85
94.77 1.0.6
16
98
DRR+
77.02 0.40
78.25
0.07
$3.80-14
0.05
$1.66
0.00
05.04 0.18
96.00
4 1616
07.
0.08
96.20 0.15
GSS
76.11 1: 1.12
78.32
0.22
79.79 J. 01.22
81.09
0.10
87.51
0.08
96.37 1. 0.49
97.61
1: 0.03
98.29 1. 0.58
GCR
76.20 + 0.34
78.12
0.22
70.00
+ 0.25
80.81
0.11
33.776 = 0.68
96.92
+ 0.25
97. 07.70
+ 0.12
98.06 + 0.05
SES (Ours)
T8.52 0.25
79.92
11.92.100 0.36
81.18 - 0.26
82.69 1. 0.10
94.73 1 0.33
96
91
0.34
96.28 0.10
98.54 0.07
27

---

Published as a conference paper at ICLR 2025
Table 19: Results for continual learning on Split CIFARIO and Split CIFARI00. The best one is bold, and the runner-up is underlined.
Split CIPARIO
Split
Daatased
CIFARIOD
Memory size
50
100
200
400
50
100
200
400
Randum
62.49 1: 0.75
62.34
0.8.
65.69 1: 1.58
65.63
20.0005 1.56
46 50
1.28
51.20 1: 0.77
51.22
0.58
56.21 1: 0.46
Moderate
61.55
61.51 0.46
0.58
65.42
0.39
61.91 0.63
53.45
8.09
56.06 0..80
00.56
1.73
0.35
Pruming
61,90 1.41
64.54
0.63
66.08
1.45
65.23
72
0.61
51.88 0.62
54.33
0.68
57.14
GruphCut
001.6 #: 1.29
61.12 =: 1:17
61.38 =: 1.67
63.51
0.77
48. 72
22 0.56
64.35
0.38
54.
0.28
56.74 = 0.33
Entropy
61.78 1 0.44
61.51 0.72
62.72 1. 0.73
63.99
1.01
45.08
1.96
47.97
1.34
51.51 1: 0.33
54.42 1 0.00
Forgetting
00.81 0.78
00.06 0.24
61 38 + 1.22
61.09
1.07
50.00
1.08
03.06
0.57
0.31 54.08
07.30 + 0.30
E1.2N
00000
67.79
58.34
0.68
1.10
48.11
0.64
AUM
68.32
0.86
70 0.73
47.20
Variunce
58.69
0.34
0.84
E-center
61.90 1.36
61.47 1.71
62.74 1.51
64.45
46.99
1,86
51.16
0.57
53.10
0.17
55.77 0.31
Grudieat Matching
00.54 =: 0.992
61.65 2 6.58
62.55 = 1.11
65.26
0.546
53.
0.886
64.13
0.53
56:29
20:29:2:00 0.21
07.24 = 0.37
FRCL
61.22 1: 1.61
61.67 1.02
02:95 1: 11.86
05.51
1.57
46.81
4: 0.71
51.40
0.44
54.28
0.55
56,01 1 0.02
ICaRL
61.35 + 1.09
02.33 +.389
64.08 + 1.08
64.09
1.15
51 67 0.71
64.62
0.51
16.11
0.32
06.90 + 0.26
Greedy Corsel
61.25 1.74
63.18 0.854
62.98 1: 0.01
65.02
1.50
52 58
0.90
56.17
0.42
5F.72 1 0.25
55.27 1 0.66
BCSR
2.86
1.25
1:14
51.49
0.42
DER++
62.65
0.38
06.06
0.10
54.10
GSSS
61.53 1 0.12
62.73 0.37
62.73
0.37
05.17
0:20
45.56
1.25
50.06
0.96
54.88
0.22
56.07 0.47
GCR
02.76 = 0.51
63.12 =: 2:35
02.25 = 11/02
66.39
2.01
46.85
4: 0.50
02.78 = 0.43
50.00 2: 0.35
06.11 = 0.33
SES (Ours)
67.52 1 0.56
68 26 1:
69.32 0.99
70.78:11
22
54.71 0.53
57. 1: 0.39
59.00 39.09.80 0.31
61.06 0.17
Table 20: Results for continual learning on Split Tiny-ImageNet. The best one bold, and the runner-up is underlined.
Split Timy-Imagee Net--mmageNNtt
Datasel
Memory size
100
200
Random
18.38 1: 0.26
18.32
01.23
19:22
1: 0.29
19:
0.26
Moderate
18.08 1: 0.30
18.63
0.36
19:47
1 6.18
19.75 0.24
CCS
18.47 4: 0.41
18.30
0.17
15.90
a 0.13
18.50
Pruning
0.10
19.08
19:50
0.14
GraphCut
19.50 +: 0.19
19.26
6.15
20.53
0.12
21.57
0.36
Entropy
18.38 4: 0.42
17.99
0.28
18.62
4: 0.22
19:20
0.25
Forgetting
18.92 1: 0.19
19:35
0.15
19.56
0.53
19.85 0.30
E1.2N
AUM
18.36 11 0.11
18.24
0.10
17.89
0.17
18.16 0.21
Variance
19:66 1: 0.02
19.32
0.07
19:50
1 0.53
20. 29
0.18
k-center
18.81 :: 0.21
0.18 18:87
18.90
0.30
19. 13
Gradient Matching
0.32
19.00
FRCL
18.59 1 0.21
18.96 0.15
19:01 0.27
19.35 0.20
iCaRL
19:05 0.44
19:58
0.18
0.16 19:85
19.86 0.58
Greedy coreset
19.61 + 0.28
19:24
0.34
0.17 19.98
20.62
0.36
BCSR
19:04 + 0.36
18.75 4:
18.74
0.17
DER+
18.20 0.34
18.86 0.34
19:00:::00 0:10
19:63 0.27
GSS
18.71 + 0.11
19:40 0.07
19:00 0.225
19:64
0.15
GCR
18.23 + 0.02
19:00 01.41
18.91 0.244
19.85
0.23
SRS (Ours)
20:40
20.80
20 0.12
0.20
Table 21: Results for continual learning under the task-incremental and task-free settings. The best one is bold, and the runner-up is underlined.
Setting
Tusk- incremental
Task-free
Memory size
50
100
200
400
100
200
400
Random
75.41
76.44 0.14
1.30)
79.78
61.35
0.60
0.00
64.25
Muderate
74.08
1
70.22
7.70
CCS
56.93 0.01
0.34
67.89
0.73
84.33
0.00
02:23
0.45
02.002 0.20
Pruming
26.75 0.26
74.47 1.11
77.03 + 0.04
80.60
6.64
61.16
0.46
64.30
+ 0.40
65.15
0.65
68.43
8.17
GruphCol
73.14 2.52
70.00 0.73
75.22
1.41
70.9c
0.71
60.01
5.11
61.26
1 0..5
63.50
4.07
63.60 1. 3.35
Entropy
74.33 0.30
73.96
0.36
75.34
4 0.82
79.10
0.64
24
1.77
63.28
4 3.41
64.79
1.86
63.56 0.16
Forgetting
65.09 1.03
58.02
0.90
58.25
0.85
71.47
0.50
63.02
0.67
1.22
61.67
0.70
64.77 0.10
E1.1N
56.38
53.86
13.02
2.04
65.23
58.95
0.76
00.51
50.28
03.08
0.37
2.50
Variance
60.07 0.46
52.45
54.50
2.54
71.81
61
1.47
66.84
1.21
1.35 65.19
63.03
64.41 1.37
Excenter
75.27 0.89
72.52
0.35
74.76
0.11
79.63
0.77
63.67
0.02
1.355
3,38
08.59 1 0.50
Grudient Matching
75.19 0.79
72.85
0.50
76.31
0.89
70.66
1.21
64.58
0.14
60.56
1.36
60.55
2.46
65.35
1.30
FRCE
75.27 2: 0.55
74.90
0.16
75.77
0.915
S0LOG
0.10
08.95 2: 01.00
62.18 4: 2.42
01:20
1177
62.54 = 0.33
ICaRI.
74.02 0.66
1.79 72.85
0.71 76.81
0.31 80.62
0.52 64.68
61.37
1.73
63/05
0.00+++2.11 2.75
62.56 0.94
Greedy Coreset
1.00
75.08
DRR+
74.30 1.12
72.33
1.38
76.86-11
0.73
70.63
8.07
00.65
1.83
60.61
1.48
61.00
1.25
64.22
GSS
75.16 0.59
75.31
0.14
76.79 J. 0.80
79.63
0.14
80.47
0.56
00.51 1. 3.06
02.85
2,30
06.18 1. 2.11
GCR
72.08 + 2.95
72.93 = 0.30
75.00 + 0.34
0.12 80.21
63.04
1.37
63.76 + 1.71
64.07
+ 3.18
02.90 + 0.62
SES (Ours)
78.71 L 0.63
80.20 1.17
81.61
0.57
82.20 0.86
06.55 1.75
6T. 0.73
66.36 1. 1.09
69.69 0.53
28

---

Published as a conference paper at ICLR 2025
G ADDITIONAL ABLATION STUDY
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. (able|2]showe the results. Using identical scores leads 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 22: Ablation of training difficulty metrics, The best one is bold, and the runner-up is underlined.
Difficulty 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
93.99
79.06
53.99
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
Quantification of node-level structural entropy. In Eq. (4). we quantify the node-level structural entropy as (.) = co[lV Σ (M..)e Wa,, log (ol(o)))) by removing the second term from Eq. (3). Alternatively, the node-level structural entropy Se(u) vV) (Σ Eu, Wi,e log vol (Oave) - d(u) log d(u)). As shown Table removing the second term slightly increases performance across all sampling rates. This finding supports our decision to remove the second term in the definition of node-level structural entropy.
retain the second term and be quantified as
Table 23: Ablation on the quantification of node-level structural entropy. The best one is bold, and the runner-up is underlined.
Quantification method
Sampling rate
70%
50%
20
10 %
5 %
2 %
1 1%
With the second term Without the second term
94.51
93.39
88.01
79.73
67.75
53.88
43.02
95.01
94.50
88.31
80.24
69.82
54.78
45.25
Methods for combining global and local metries. We explore possible alternative methods to combine the global metric (u) and the local metric Su(u) other than the proposed multiplication. (s)).. Specifically, experimented with the sum (S. (u) (u)), the harmonic mean (. ) and the maximum (max(S, S. (u), (u)))). As shown Table 24 multiplication achieves the best average performance, validating our choice for combining the metrics.
Table 24: Ablation different combination of S. and S.. The best one is bold, and the runner-up is underlined.
Combination 70%
Sampling rate
Avg.
method
50%
20 %
10 %
5%
2 %
1 1%
(u) + (T)
94.77
94.43
87.17
79.64
69.08
53.24
44.53
71.35
(.)
94.84
94.64
88.11
79.97
69.75
53.95
44.88
71.88
(.))+)((()) max S. (w), (u))
94.22
93.22
87.24
78.33
68.49
53.04
43.30
70.60
(u) (.)
95.01
94.50
88.31
80.24
69.82
54.78
45.25
72.15
Replacing graphs with hypergraphs. We have conducted an experiment using hypergraphs (Zhou al. 2006) to capture the relationships between samples. Following Feng al. (2019). we construct a hypergraph by adding hyperedge for each node that contains the node itself and its k-nearest neighbors. Due the lack of the structural entropy theory for hypergraphs, apply clique
29

---

Published as a conference paper at ICLR 2025
expansion (Agarwal et al. 2006), which creates edge between every pair of nodes in hyperedge, to convert the hypergraph into a graph. We then apply our selection method to the resulting graph. Table showws the results. This hypergraph-base based method slightly degrades performance compared to the graph-based method, but still performs better than the baseline methods low-sampling- rate settings. We attribute this slight decline in performance the information loss during clique expansion, for which straightforward alternative is not currently available. We see significant potential for future work in developing structural entropy theories for hypergraphs and then applying our method to sample selection.
Table 25: Ablation study replacing graphs with hypergraphs. The best is bold, and the runner-up is underlined.
Graph Type 70%
Sampling rate
50 %
20% %
10%
5%
2%
%
Hypergraph
94.81
94.37
88.12
80.05
69.30
54.50
44.72
Graph 95.01
94.50
88.31
80.24
69.82
54.78
45.25
Effect of k in the kNN-graph construction. We test the effect of k in the kNN-graph construction. Fig. shows the results when selecting 10% of the samples from CIFARIO. As 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.) [220). Based on the grid search results across datasets, empirically determine logg n to be an appropriate value for k. where n is the number of samples.
80.5
ACC.00)
80.0
79.5
79.0
70.5
80
k
Figure 5: Ablation of k in the kNN-graph construction.
30

---

Published as a conference paper at ICLR 2025
H FULL QUALITATIVE RESULTS
Fig. 6 visualizes the results of different methods when selecting 2% of the samples from CIFARIO. Methods that select the most difficult samples, such AUM, oversample near several class boundaries and undersample in several classes that are easier to classify. Methods that prioritize sample coverage, such ID² Pruning and CCS, achieve 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 set of informative and representative samples for model training.
(a) Random
(b) AUM
(c) EL2N
(d) Forgetting
(e) Entropy
(f) Variance
(g) Moderate
(h) GraphCut
CCS
① D2 Pruning
(k) SES (Ours)
Figure 6: Visualizations of selection results of different methods when selecting 2% of the samples from CIFARIO.
31


Reviews:
[{"review_id": "S59e6prU5K", "reviewer": "Reviewer_MHqY", "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.\n\nThe 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.\n\nThe 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.", "questions": "Are there anything you can prove about the node-level structural entropy values?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 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.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0R6vrCGi4F", "reviewer": "Reviewer_g3Pt", "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.", "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?\n\n2, 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?\n\n3, 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))?\n\n4, 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)?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 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.\n\n2, 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.", "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? \n\n2, 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.\n\n3, 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.\n\n4, 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.\n\n5, 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.\n\n6, 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0fld6XLqQe", "reviewer": "Reviewer_4FM2", "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. \n\nThe main contribution of this paper is to propose a new global metric for sample selection.", "questions": "Please see the weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.The writing of this paper is good and easy to follow.\n\n2.This paper has a certain degree of innovation, introducing a structural entropy as a 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.\n\n2. How would the authors define informative and representative samples? They mention these concepts multiple times, but do not provide a detailed explanation.\n\n3. 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.\n\n4. The experimental results do not show the variance, so I hope the authors can make up the variance.\n\n5. 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?\n\n6. 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.\n\n7. 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?\n\n[1] Learning with hypergraphs: Clustering, classification, and embedding.\n\n[2] Hyper-class representation of data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NQYb2QDj97", "reviewer": "Reviewer_j2F4", "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.", "questions": "Please see Weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The idea is interesting and reasonable.\n2. The experiments are sufficient and the experimental results are good.", "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.\n\n2. 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.\n\n3. 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).\n\n4. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)