Accelerated Deep Active Learning with Graph-based Sub- Sampling
Authors: Dan Kushnir
Shiyun Xu
Venue: Accepted by TMLR ()

Abstract: Past years have witnessed the fast and thorough development of active learning, a human-in-the-loop semi-supervised learning that helps reduce the burden of expensive data annotation. Diverse techniques have been proposed to improve the efficiency of label acquisition.  However, the existing techniques are mostly intractable at scale on massive unlabeled instances. In particular, the query time and model retraining time of large scale image-data models is usually linear or even quadratic in the size of the unlabeled pool set and its dimension. The main reason for this intractability is the iterative need to scan the pool set at least once in order to select the best samples for label annotation.

To alleviate this computational burden we propose efficient Diffusion Graph Active Learning (DGAL). DGAL is used on a pre-computed Variational-Auto-Encoders (VAE) latent space to restrict the pool set to a much smaller candidates set. The sub-sample is then used in deep architectures, to reduce the query time, via an additional standard active learning baseline criterion. 
DGAL demonstrates a query time versus accuracy trade-off that is two or more orders of magnitude acceleration over state-of-the-art methods. Moreover, we demonstrate the important exploration-exploitation trade-off in DGAL that allows the restricted set to capture the most impactful samples for active learning at each iteration.

Published in Transactions on Machine Learning Research (07/2024)
Accelerated Deep Active Learning with Graph-based Sub- Sampling
Dan Kushnir Bell Laboratories NOKIA
dan.kushhir@@noiio-bllllbbbbb...
Shiyun Xu
Chignmanu@sus..ueeeee edu
Department of Applied Mathemalics and Computational Science University of Pennsyloania
Reviewed on OpenReview: https: // openreview. net/ pdf? id= iBorskJJRr
Abstract
Past years have witnessed the fast and thorough development of active learning, a human-in- the-loop semi-supervised learning that helps reduce the burden of expensive data annotation. Diverse lechniques have been proposed to improve the elficiency of label acquisition. However, the existing techniques are mostly intractable at scale on massive unlabeled instances. In particular, the query time of large-scale image-data models is usually linear or even quadratic in the size the unlabeled pool set and its dimension. The main reason for this intractability the iterative need scan the pool set at least once to select the best samples for label annotation.
To alleviate this computational burden, we propose efficient Diffusion Graph Active Learning (DGAL). DGAL used pre-computed Pariational-Auto- Entloersss (VAE) latent space to restrict the pool set to much smaller candidate set.. The sub-sample is then used in deep architectures, to reduce the query time, via additional standard active learning baseline criterion. DGAL demonstrates a query time versus accuracy trade-off that is two or more orders magnitude acceleration over state-offthe-art methods. Moreover, we demonstrate the important inerration-expliitattinn trade-off in DGAL that allows the restricted set to capture the most impactful samples for active learning at each iteration.
1 Introduction
Deep learning has provided unprocedented performance in various semi-supervised learning tasks, ranging from speech recognition to computer vision and natural language processing. Deep Convolutional Neural Networks (CNN), in particular, have demonstrated object recognition that exceeds human performance. However, this success comes with the requirement for massive amounts of labeled data. While data collection at large scale has become easier, its annotation with labels has become a major bottlenock for execution in many real-life use cases (Settles] 20099 Ren al.) 2021). Active learning provides a plethora of techniques select a set of data points for labeling which optimally minimizes the crror probability under a fixed budget of labeling elfort (see (Settles (2009) for review). As such it is key technology for reducing the data annotation effort in training semi-supervised models.
One of the key caveats in active learning, preventing it from being used on an industrial web scale, is the computational burden of selecting the best. samples for annotation al each step of active learning. This complexity is rooted a variety of important criteria that need to optimized in active learning. Referred as the 'two faces of active lcarning' Dasgupta (2011), the most common selection mechanisms can be categorized into two parts: uncertainty (c.g- Lewis & Gale (1994)) and diversity sampling (e.g Ash al. (2019a) Sener & Savarese (2077a)). The intuition of the former is to select query points that improve the

---

Published in Transactions on Machine Learning Research (07/2024)
model as rapidly possible. The latter exploits heterogeneity in the feature space, sometimes characterized by natural clusters, to avoid redundancy in sampling. The combination of the uncertainty and diversity
criteria has been an important subject of recent works Yuann et al. 2020 Zhu et al., 2008; Shen et al.
2004; Ducoffe & Precioso 2018 Margatina et al., 2021 Sinha et al. 2019a Gissin & Shalev-Shwaid 2019
Parvaneh et al. 2022 Huijser & van Gemeri, 2017: Zhang el al.
2020
Optimizing for uncertainty or diversity (or both) may require scanning all data at least once, and typically requires methodologies with computational costs that scale quadratic or more in the unlabeled pool size (Bodó et aL,, 2011; Tong & Koller 2001; [Snnr & Savarese, 2017a). A standard active learning cycle repeats the time-consuming model (re- tre-)training and query selection process multiple times. In many cases, these cumbersome repetitions render active learning impractical on real large-scale data sets. Even a single feed-forward process in a deep learning network for uncertainty calculation (e.g. Gal et al. (2017)) may impose a significant delay in query time. may scale non-linearly in the dimension of the data (e.g. number of pixels) for each query candidate in many deep network architectures, where fully connected layers exist. To this end, only a few approaches have been suggested to overcome this bottleneck in the context of deep learning. Most notable is SEALS Coleman et al. (2022a), which improves the computational efficiency of active learning and rare class scarch methods by restricting the candidate pool for labeling to the nearest neighbors of the currently labeled set instead of scanning over all of the unlabeled data. The restricted set is given as an input to the task classifier for a second selection step, and using a second basic uncertainty criterion, a final query set is selected for annotation.
We identified that the SEALS criterion of selecting k-nearest neighbors to the restricted pool does not address the diversification criterion in query selection. It also does not capture the exploration-refnemne which improves active learning tremendously, Therefore, we propose different algorithm for the selection of the restricted pool set based on a graph diffusion algorithm inspired by (Kushnir, 2014 Kushnir & Venturi 2023). We refer to it as Diffusion Graph Active Learning (DGAL). In DGAL, the proximity graph is computed only once for a latent Variational Auto Encoder (VAE) Kingma & Welling (2013) reprosontation space which is trained (without supervision) once prior to the annotation cycles. This graph representation is then used for a label diffusion process to select the most diversified and uncertain candidates in time that is log-linear in the data size (Appendix 4.4). The graph, computed only once, allows faster lincar query time in each diffusion process, unlike SEALS Coleman et al. 2022aa) whose query time keeps growing by a factor dependent linearly on the number of neighbors k.
transition
As seen in the overview of our method in figure our method is comprised of two components: a representation component in which a VAE training occurs once and is used to generate a proximity graph that is then shared in the iterative stage of the active learning component. We note that other representation spaces may also be considered for graph construction. A label diffusion process on the graph is used throughout the active learning iterations, in the second component, to select restricted and small set of candidates which is fed into the classification neural net for the final query selection (e.g. uncertainty sampling (Lwis & Gale, 1994), margin (Scheffer et al. 2001), etc.). As shown in our paper the restriction to smaller set via our graph construction accelerates active learning while achieving state-of-the-art or better accuracy.
The graph-based diffusion algorithm used in DGAL enhances an important criterion in active learning referred to as the exploration-cxploiaatee (or exploration-rcfiemeet criterion). Exploration addresses a stage active learning in which data are sampled and annotated to first map decision boundaries in the data. On the other hand, exploitation takes the so far detected boundaries and samples points around them to further localize the boundaries. At the early stages of AL, an exploratory strategy typically yields better gains in accuracy over boundary refinement. However, once all boundaries are detected, typically a refinement stage provides better accuracy gains over further exploration. This important trade-off is not leveraged in standard simple AL criteria such as probabilistic uncertainty sampling or diversification per se. In particular, a k-nearest- neighbrrs to the training set [Coleman et al. (2022a)) also does not reflect this trade-off. We demonstrate in this paper that our combined graph methodology for pool set restriction improves AL query time and scales it to large-scale data sets. We summarize our contributions below:
2

---

Published in Transactions on Machine Learning Research (07/2024)
We propose DGAL, two-step active learning algorithm, that starts with restricting the pool set to smaller set using graph-diffusion process and then uses the restricted set to perform deep active learning efficiently.
DGAL achieved orders of maguilude acceleration in query time compared to state-oftthe-ar (SOTA) active learning schemes, while maintaining the most competitive accuracy.
1 9
9
9
9
VAE training
Encoder
Decader
Learn latent representation
7
Latent graph diffusion
9
Full data w/o labels
Variational Auto-encoder
Latent space
Optimized Representation (Single Pass)
Label information
Labeled training set
Re-training
Similarity graph
Task model
Annotate selected queries
Query candidates
Final label query
Active Learning Cycle
Figure 1: Overview of the DGAL approach. A Representation component that involves a single pass the data for deriving VAE-based latent graph representation. An Active Learning iterative component that uses the VAE latent representation graph in conjunction with existing label information to sclect a restricted set of query candidates. The set of candidates is fed into a task neural net, where second criterion is used to select the final label queries for annotation.
2 Related research
Efficient Active Learning. With the increasing availability of large-scale unlabeled datasets, traditional active learning methods are too computationaly demanding to apply. This problem has motivated the development of more compact, elficient. AL algorithms to cope with large-scale data sets/models. In SEALS Coleman et al. (2022a) the candidate pool is restricted to the k-Nearest Neighbours (KNN) of so-far-labeled instances, to avoid the computational burden of batch selection with large pool sets. However, the KNN set is typically very similar to the already labeled training data and therefore its information content for improving the classifier low. This lack of diversification and exploration accuracy. Moreover, the number of nearest neighbors being fed later to the tasks neural is growing by a factor of l on each query step. This leads
SEALS yields sub-optimal
increasingly higher query time when the restricted pool is fed into the task network. Xie et al. (2021) propose knowledge clusters extracted from intermediate features over pre-trained models by single pass. Ertckin et al. (2007): Doucctte & Heywood (2008) proposed to actively subsample unlabeled candidates under imbalanced datasets in general learning schemes, different. than deep learning. Generating informative samples Mayer & Timofte (2020): Huijser & van Gemert (2017); Zhu & Bento (2017) saves time from the unlabcled data acquisition aspect. Small but well-trainod auxiliary models have been used select data to reduce the computational cost of extracting feature representation from the
unlabeled pool (Yoo & Kweon 2019 Coleman al. 2019
3

---

Published in Transactions on Machine Learning Research (07/2024)
Graph-based Semi-Supervised Learning (GSSL) Semi-supervised learning (SSL) Zhu (005 exploits the information of both the labeled and unlabeled datasets to learn a good classifier. As a form of SST, active learning automates the process of data acquisition from a large pool of unlabeled datasets for annotation to
achiove the maximal performance of the classifier (usually) under a limited budget. GSSL (Zhu 2005; Song
eet al. 2022 Zha et al. 2009) is a classic branch of the SSL, that aims to represent the data a graph such that the label information of the unlabeled set can be inferred using the labeled data. A classic and solid technique is label propagation or Laplace learning Zhu et al. (2003), which diffuses label information from labeled sets to unlabeled instances. Notably, the computational complexity of typical label propagation alg algorithm is only linear in the size of the data, which renders them efficient choices for learning.
The success of label propagation hinges on an informative graph that retains the similarity of the data points. Due to the volatile property of image pixels, i.e., unstable to noise, rotation, etc., feature transformations
Lowe 1909: : Bruna Mallat (2013); (Smonyan & Zisserman (2014) are usually applied to build good quality
graphs. Past rescarch Doersch (2016); Kingma et al. (2019): : Mei et al., (2019); Miller al. (2022); Calder
et al. (020) has shown that the VAE can generale high-quality latent representation of data for fealure
extraction and similarity graph construction. We utilize these properties in our DGAL framework.
Generative Models in Active Learning. Deep generative models have been used to learn the latent
representation of data in both semi-supervised and unsupervised learning [Kingma et al. 2019 2014p. Except for constructing similarity graphs in GSSL, they can also be exploited to generate adversarial data/modes for more efficient and robust AL. For example, [iina et al. (2019a) proposed a task-agnostic model that trains an adversarial network to select unlabeled instances that are distinct from the labeled set in the latent space of a Variational Auto-Encoder (VAE). The DAL Gissin & Shalev-Shwartz (2019) selects samples in a way such that the labeled and unlabeled sets are hard to distinguish in learned representation of the data, Miller et al. (2022) embeds the Synthetic Aperture Radar (SAR) data in a latent space of VAE and applies a GSSL method on a constructed similarity graph in this feature space. [Pourkamali-Anatee Anaraki & Wakin 2019
aims at finding a diverse coresct in a reprosentative latent space using K-Mcans clustering.
3
Problem setup and preliminaries
3.1
Active Learning
We consider a data set D E I&d of cardinally [n]. D can split into a labelled set Dj which represents a
Algorithm 1 A general active learning algorithm
Input: Labeled data D1, unlabeled pool Du. batch size B, maximum round R, task model fo Initialize D; by random sampling and train fo on for i 1 to R do
labeled subset of D. and an unlabeled subset Du- C denotes the nunber of classes. Fixing a batch size B, we seek for the most 'informative' subset D* E D, to be annotated from an unlabeled pool set given limited budget for annotation.
query DQ + QueryStrategyl fe, Du, B) update D; + D, DQ. Du + D. \ DQ train model fa on new labeled pool Dj
Active Learning Problem Statement. Tet So be a classifier: fe: R2 + Ac, (Ac denotes the space of probability measures over [C] = (1....CC) CT). Assume data are sampled i. over a space D (C), denoted (x,, y4 he(n) We would like to find subset D3 c D2 of cardinality B such that for classifier fo trained with D; Di
end for
D3 = arg min En,eE (TJo(t)) *bll Do: Do =B
(1)
gives the minimum expected error. Clearly, finding D2 C D, that minimizes 1 is not possible without knowing the labels. Hence various active learning strategies to approximate Dē have been developed in the literature. To summarize we provide the general active learning framework in algorithm
Query Time. Query time the time measured between the activation of the query strategy and its return with a selected set, i.e. first line in the loop of Algorithm 1
4

---

Published in Transactions on Machine Learning Research (07/ (204))
3.2 VAE-based data representation
Latent variable models such the VAΣs are well-acknowledgedd for learning representations of data, especially images. VAE is a generative neural network consisting of a probabilistic encoder (</2z) and generative model p(a|z). The generator modcls a distribution over the input data z, conditioned on a latent variable x with prior distribution po(z), for simplicity we omit the subscript A. The encoder approximates the posterior distribution p(=(æ) of the latent variables z given input data x and is trained along with the generative model by maximizing the evidence lower bound (ELBO):
ELBO(s) Eg(=te) (og((((()]]) -LL((()))))
where KL is the Kullback Libeler divergence and log(p(x)) ELBO(a).
To get representative latent space from data (without label information), we use ResNet18 (He et al., 2016) based encoder for large datasets and CNN-based VAE for all other datasets. In the first term, [pg] 1 E. (x;-=()) where x is the i-th (out of n) reconstructed image. We use the MSE loss for the first term, i.e. the reconstruction loss. Next, we construct a proximity graph from the latent representation to be used within a graph diffusion process and label acquisition.
4
9
4
9
4
9
Figure visualizes a 2D projection of CNN-VAE 5D rep- resentation of digits '4' and '9' from the MNIST dataset. To demonstrate the important semantics of this representa- tion for active learning, we focus on the decision boundary between digits. we observe samples of '4's that are similar to samples from the '9' class along the boundary.
4
C
-3
-2
-1
Figure 2: A VAE representation of digits '4' and '9' from MNIST.
4 Methodology
Below we explain the various components of VAE-DGAL and then connect them to provide the overall DGAL scheme. Active learning is used in DGAL in similar scheme to what is proposed in algorithm ! However, we are using an active critcrion in two components: first, we use a very efficient grapb-diffusion- basod selection criterion Kushnir & Venturi (2023) in the VAE latent space to restrict the pool set to a much smaller set of candidates. In the second component, we use a second acquisition criterion to select from the set of query candidates the final query set for annotation. The second selection criterion may be computationally intensive due to its nature, but also because it requires feed-forward transmission. However, when applied to smaller, restricted set can be executed extremely fast.
We provide the pseudo-code of our method in Algorithm 2 We note that the imput to VAE-DGAL includes the labeled and unlabeled pool set, the VAE architecture, and the task classification nelwork fo- After training the representation model g, we initiate active learning cycles which include i) diffusion- based selection for restricting the pool set, ii) foeding the restricted set to the task network fo and, iii) using a basic active learning criterion select the final set. After annotating the final set, fo is retrained. The time complexity analysis showing a log- linear complexity can be found in Section 4.4
The VAE representation space can be replaced by other representations. Its advantage is in being derived via an unsupervised mothod which requires no labels and can be performed only once, prior to label acquisition. The underlying assumption is that the representation space bears a structure that correlates with the class function, and therefore can be used to restrict the pool set to a smaller, yet, impactful set of candidates for annotation.
4.1 Diffusion on graphs
Consider the optimized latent representation g(D) = Z, where g: Rd - RR,, and k is the dimensionality of the latent space Z. Z may also be divided into a mapping of the labeled and unlabelled set Zi and Z...
5

---

Published in Transactions on Machine Learning Research (07/2024)
respectively. In this latent space, we construct weighted KNN proximity graph G (V, E), where the nodes V correspond to the latent space representation of the data points E 7., and the edges F. correspond to the pairs (y) corresponding to (2i, who are neighboring in Z. The edge weights are computed as
We m (-
IÍ E N(O)
Tij
with : (2); 2,) + Ry similarity metric, P distance metric, dij as local scaling factor, and N(i) the K-NN neighbourhood of node in the latent space. We define graph transition matrix M by
A
(2)
where A (E, Wiy)- M stands for the transition probabilities of Markov random walk on G.
We construct label diffuusio framework a Markov process to propagate the label information from the labeled set Dj to the unlabelled set Du. The transition probability of step from state i to state j is Mýj. W.l.g. consider binary classification and the labeling function v(=) {-1,1} to facilitate the following: we associate the classification probability p(v(2;) = 1[22) with a t-step hit probability (:((2)) = 1|t) of a random walk from 2; to a training sample 2 with label 1. We can therefore predict the label '1' to 2; in Zn based on the random walk probability (z(((2) = 11:). pr(2(2)) = 1/i) can be derived by the recursive relation
Pr(u(2) 1|:) Σ Pr- (g)1(((2) 115)
Let X; = = - - denote approximation to the binary label function of a node We also denote Xa and Xi as the entries corresponding to the unlabeled and labeled node sets in X. respectively. In matrix form we can rewrite 3 for
Xa [A (w W Wanl
X1 Xu
where A = -Aur
0 ) w = Ann
Ww Wat
Wio Wan
(4)
We can rewrite
4 the graph Laplacian L = D - W in the system
LuuXu WWXX Luuxuu Lout!
(5)
Equation
above can be solved via the iteration Chapelle el. al.
2009
((+1) 1 X;
Σ Lun.si (1) jz1
(6)
Lunnss
where the superscript corresponds the iteration index. Equation 6 is transducing, at time step (t 1), a label t+1 to X: a weighted average of the labels of its neighbors at time step t.
Now consider the multi-class case, X is now an C matrix. For the signal column vector corresponding to the class E C, the diffusion process initializes with
{
if 2; E Zi and c == y1
Xic
if 2 E Zi and c + y:
(7)
if 24 E Zu
The labels are propagated to Xa gradually for t steps. At the (t + 1)-th stop,
( 1 1
if E Z, and c =
Xic
(1+1)
{
-1
z; E Z and e + yA
(8)
(Mx
21 E Zy.

---

Published in Transactions on Machine Learning Research (07 /224)
Long legs
50
4
40-
30
9
9
20-
Short logs
d
4
0
9
q
-40
-10
-40
-30
-20
-10
50
440
20
Figure 3: The DGMG selection of digits 4s and 9s (from MNIST) in an embedding space of ResNet188 well-trained with full data and labels.
Figure 4: The DGMG selection of CIFAR10 in a ResNet18 embedding space. The dark dots are selected points by DGMG.
4.2 Query criterion
To this end, the diffusion process can be used to probe the most uncertain points. Most uncertain points maximize the gradient of the loss function in expectation and therefore will reduce the expected error in the model in Equation (L) Active learning, therefore, aims to query points of highest uncertainty.
The matrix (T)) of propagated values at time T can be interpreted as uncertainties measured by the absolute value 1x_7 Specifically, the absolute value magnitude represents a measure of uncertainty on whether vertex belongs to class c. The magnitude can be used to select the new batch to query as
Da = fo+ arg min min (2)
Ix 1|}
(9)
cE(C]
where min B denotes the B smallest elements.
We demonstrate the exploration-refnemmnn trade-off of (9) in Figure 3 with a subset of MNIST (LeCun et al. 1998) representation in a trained ResNet (He et al. 2016). A higher query rate is observed close to the decision boundary after the overall clusters have been explored (queried samples are in bold round points). We also demonstrate that the query selection along the boundary captures '4's and '9's that have similar shapes, 'leg' sizes, and orientations. These samples whose similarity can be best learned via annotation are automatically selected by our criterion ( for annotation.
In Figure f we plot the latent representation of CTFAR1O (Krizhevsky et al., 2009 We mark the points selected by the first five rounds as dark, round dots and data selected by the next five rounds as rectangular, dark dots. Different color stands for different classes and points with lighter colors the latent representation of all the CIFARIO data. Here similar trend is captured showing the sample selection starts with exploration and then tends to the refinement of decision boundaries between clusters of different classes.
Exploration and Refinement. Our query criterion coupled with the diffusion process allows us to explore the data set at the early stages of active learning and switch to refinement when exploration has saturated. To understand this mochanism we show in the following that the diffusion itcrant x" converges to the second eigenvector Φ2 of the graph's Laplacian as + do. Asymptotically, Φ2 provides relaxed solution to the minimal normalized cut problem, where the cut corresponds to the decision boundary between the two classes in G(V. E, W).
At early stages of label acquisition low magnitude ude entries in x correspond to data points that are unreachable from the training set via diffusion and need to be explored. At later stages, all unlabelled data points X, are reachable via diffusion from the labeled set X,. At this stage low magnitude entries correspond to the transition between the two classes -1 and 1. These nodes capture the eigenvector's transition from negative to positive entries. Therefore, sampling these points for annotation corresponds to the refinement. of the
7

---

Published in Transactions on Machine Learning Research (07/2024)
decision boundary. We provide the main theoretical result on the convergence of (()) and refer for further details in Kushnir & Venturi 2023).
Lemma 4.1. Let X1, An, 61, ,.. On be the solutions to the system: Lo - A)D Then x0) converges to 22 via the iteration (6) with M, as 00.
4.3 Deep active learning with the task classifier
At the last stage of the algorithm we in- put the restricted subset Dau into the task net and using a baseline active learn- ing criterion we select the final set Do be sent for annotation. Feoding pool data into the network poses a significant. computational cost. However, since the restricted set Dauh is significantly smaller than Du we observe a significant speedup in the query time. In our experiments, we used two simple baselines to demon- strate the speed of DGAL. However, any other deep active learning criterion can be used, including another diffusion-based criterion (Kushnir & Venturi 2023
Algorithm 2 The DGAL strategy
Input: Labeled data Dı, unlabeled pool Du, the initial VAE model 9, the lask model Sa, T, K, batch sizes B1 round R, a query strategy Q
Train 9 with the full dataset (without label information)
Build graph G = (V, E, W) from the latent space g(D) = for r = to do Initialize (0) based on Dr
for t 1 to T do
x +- (x
assign x() with training labels end for
Query a restricted set of size B
D = {x, 24 arg zin lice
(T)
Least Confidence. Confidence sam
Active sub-sampling of batch Dith with criterion Q
pling (Lewis] p995p: 24 = arg max, (1 [a(x)), where (xx) is the prediction proba- bility extracted from the output layer and arg max fx). Denoted as DGLC. Margin. Margin sampling (Scheffer et al.) 2001 x² = arg min (x) Jzg (.)); where é1, 82 are the first and second most probable prediction labels respectively. Denoted as DGMG.
and network so: DQ + QUo, Dar B2)
Annotate DQ
Update D1 +- DiU D. t Du DQ
Train fo with Dr. end for
4.4
Computational complexity analysis and parameter selection
The rumning time analysis is composed of three parts. The first part inchudes the computation the K-NN graph. The K-NN proximity search computational cost can be reduced from the naive search cost. by using procedures for K-NN search based on KD (Bentley 1975) or ball trees (Omohundro) 1989). Such methods have complexity O(dN log N), with d the dimension of the space. Other alternatives include approximate search (Datar al. 2004). In the second part, the diffusion vector x is multiplied by the transition matrix. Addressing its sparsity as O(KN) non-zero entries, this operation scales linearly in N as O(TKN). T and K determine the level of confidence imposed by the diffused training set over the unlabeled set. Higher K imposes strong confidence in the current labeling hypothesis but renders the diffusion more exhaustive. Similarly, a large number of iterations may result in an overly smoothed (and less informative) signal (T). During exploration, large T imposcs hypothesis that may be locally correct but is far from being globally reliable. In our experiments, we use T < logg N to cover most of the graph via diffuusio: assuming diameter-balant balanced graph (S. Miklavic, 2018). The cover requires Oloog N) iterations if the labeled set is small (i.c. |X| x O(1), as typical in active learning settings). We use K sufficiently high to allow graph connectivity. This parameter selection leads to diffuusin process that scales as O(K N logg N).
Finally, a batch of the smallest soft-labels needs to be queried. This requires a quick-sort to be applied the soft labels magnitude, which scales O log N). We conclude that the running time of DDAL is O(dN log N KN KNlogg N + N log N), whereas for constant K can be further simplified to O(dN M(dNlog.) N). We note that the number of units in the penultimate layer d is typically small.
8

---

Published in Transactions on Machine Learning Research (07/2024)
Additional parameters: The batch size B is set at no more than 500 (sce batch size for diffusion algorithm in Kushnir & Venturi (2023). The number of epochs is set with a stopping criterion for the convergence of the loss function.
5 Experiments
Our experiments validate our goal to reduce the query time while maintaining the highest accuracy. We report DGAL's improved query time vs. accuracy trade-off and compare it with pivotal SOTA baselines. Additionally, we provide classical active learning empirical analysis of the trade-off between the number of queried data points and accuracy, and we provide average query times, for all baselines and data sets. We provide an ablation study with VAE-SEALS (see Algorithm 3 and with random versions of pool set. restriction, Training details are provided in table ! in the appendix.
5.1 Benchmarks
selects samples uniformly at random for annotation. Confidence based methods: A set of conventional selection strategies includes Least- Coas--Confieecce (LC) (Lewis) 1995), Margin (Schelfer et al.) 2001 Luo al., 2005) and Entropy (Holub et al,, 2008). In LC, the instance whose prediction least confident is selected; Margin selects data that has minimum difference between the prediction probability of the first and second most confident class labels. Entropy selects samples that are the most uncertain overall class probabilities on average. BADGE (Ash et al. 2019a b): Selects points based on their gradient magnitude
Random:
and diversity. CoreSet (Sener & Savarese, 2017a by: An algorithm that selects a core-set of points that
A-cover the pool set. SEALS (Coleman ct al. 2022a b restricts the candidate pool to the nearest neighbors
of the currently labeled set to improve computational efficiency. We examine two versions of SEALS, one that updates the feature extractor, and another that sets it fixed using a VAE. GANVAE (Sinha al., 2019a b): A task-agnostic method that selects points that are not well represented in the pool, using VAE and an adversarial network.
Data sets and setting. Experiments are conducted on multiple data sets to evaluate how DGAL performs in comparison to SOTA benchmarks. We also perform an ablation study. We experimented with benchmark data sets MNIST LeCun et al. (1998). EMNIST Cohen et al. (0017). SVHN Netzer et all (2011), CIFAR10 Krizhevsky et al.] (2009), CIFARIO0 Krizhevsky et al. (2009), and Mini-ImageNNet Ravi & Larochelle) (2017) data sets. We include classic networks CNN LeCun al. (1998), ResNet18 He al. (0016), ResNet50 He et al. 2016), and ViT-Small Dosovitskiy et al. (2020).
5.2 DGMG vs. Benchmarks
Query time vs. test accuracy. In Figure 5 we report accuracy per total query time for a fixed number of queries. We observe for all data sets that DGMG's accuracy per query time is by far higher than SOTA. Morcover, emphasize its ability to reach the highest accuracy vs. the random baseline, which is the fastest method with essentially close zero query time (approx. 10-3 secs.). It can be seen that the acceleration of DGAL is of an order of x1000 with respect to the worst benchmark method and x100 concerning the next best-performing method. These results emphasize the advantage of the DGALs graph diffusion approach in selecting more impactful samples for the pool set restriction, in particular, the advantage over using the n-nearest-niihhbors to the existing training set, as proposed in SEALS. The KNN criterion does not select a diversified set or even focus on docision boundary refinement in the restricted set. Consoquently, its accuracy gain in each query step is lower. Additionally, the ever-growing candidate size in SEALS (by a factor of the number of neighbors) increases the total query time.
We note that in our experiments for Figure 5 the SEALS feature extractor is trained with labeled data before any acquisition cycles by using a part of the labeled data to implement the KNN data structure. The remaining data serves for pool acquisition. Such an approach does not apply to active learning where initial labels may not even exist unless transferred from a pro-trained model, as suggested in Coleman et al. (2019). To provide a consistent benchmark, ie. applying SEALS in the same way for all datasets, we adjust the algorithm by feeding the datasets into the trained task model to get embedding representation as the
9

---

Published in Transactions on Machine Learning Research (07 /224)
Total Query Time (5
400
500
BADGE SEALS Coraded EMt00p
Total Query Time L
2500
3000
BADGEE
GAMAEE
1750
1500
84D0E
GAMAF
SCALS
Total Query Tima
1250
2000
1000
DEMG
R5
1300
750
1000
100
500
20
20
Test Accuracy
Test Accuracy
Accuracy
(a) MNIST
(b) EMNIST
(c) SVHN
MAGE
BADICE
3500
Total Query Time 6
2500-
2000-
Condiet
SE485
Entrapy
Total Query Time
2500
2000
SEALS
Conseet
Entrosy
Total Quary Time
2500
2000
SEALS
RJ
Conddet
Entrayy
1500-
2000
2000-
1500-
1000
1000
1000
300-
500
500
30
60
50
10
20
40
70
20
30
40
90
90
Test Accuracy (%)
Test Accuracy (16)
Test Accuracy (%)
(d) CIFARIO
(e) CIFAR100
(f) Mini ImageNet
Figure 5: Plots of total query time vs test accuracy for 6 datasets over 6 benchmarks. The vertical lines capture the highest and lowest test accuracy among all methods.
feature extractor, which adds up query time. Below, we demonstratc a version of SEALS using a VAE as the feature extractor to compute the KNN graph only once. From a later experiment, we found that VAE-SEALS is slower than DGAL in query time and worse in its query-vs-accuracy trade-off.
Test accuracy vs. number of sclected labels. In Figure D we report the classical active learning tradc-off between accuracy and training set size. DGAL is observed to be competitive with several SOTA benchmarks, in particular, BADGE of |Ash et al. (2019a) and CoreSet of [Sener & Savarese (2017ap. SEALS,, on the other hand, is observed to be lagging in several data sets in an early stage of active learning because its selection criterion relies on the nearest neighbors of the existing training set which does not diversify the restricted set enough. Tn fact, its accuracy in the late stage does not even get close to existing benchmarks because refinement is not occurring either in the nearest neighbor- based query criterion.
Average query time. In Figure 7 the DGMG's average query time is an order of magnitude lower than that of all benchmarks. Note that the RS has an almost zero query time (at most 10-3 secs) that is barely visible in the plots.
VAE and graph construction time. We provide running time for the VAE and graph construction Table in the appendix. As seen, even with the pre-processing time our method is still faster than other methods, in particular, faster than the SEALS algorithm without its additional pre-processing time. We note that the pre-processing lime is a one-time procedure, while the query is repeated process, depending on each case. Hence, total query time can increase significantly higher than the pre-processing time. Hence the advantage of reducing it even with the price of pre-processing time.
5.3 DGMG vs. VAE-SEALS in accuracy and query time
We compare DGMG and DGLC with VAE-SEALS (sce Algorithm In VAE-SEALS, instead of extracting the features of unlabeled data from the task model and re-computing its KNN graph at each round, we use the same VAE latent space as used in DGMG. We note that in the SEALS paper Coleman et al. (2019), the authors didn't 't specify a specific representation space in the algorithm. This ablation study verifies that our query component based on diffusion is outperforming the KNN criterion of SEALS. We provide the results for this experiments in Figure below and figures 10 and 11 in Appendix D.T. This study provides different.
10

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Test Accuracy (%)
Test Accuracy (%6)
CHeC
50-
Test Accurac 30
50-
6.3
40
30
Cendae
Naves
DOING
50
100
150
200
250
300
200
400
6:00
BD0
1000
500
1000
3500
2000
2500
Number of Labels
Number of Labe
Number of Labels
(a) MNIST
(b) EMNIST
(c) SVHN
80-
Test Accuraty (96)
00
(66)
70
70-
Test Accuracy
70
50-
60
50
BA002
30-
40
30
500 1000 1500 2000 2500 3000 3500 4000 Number of Labels
500 1000 1500 2000 2500 3000 3500 4000 Number of Labe
500 1000 1500 2000 2500 3000 3500 4000 Number of Labels
(d) CIFARIO
(e) CIFAR100
(I) Mini ImageNet.
Figure 6: Plots of test accuracy size of queried data. Each experiment is run at fixed query rounds for different methods and has been repeated 5 times.
60-
30
Query Time (s)
50-
Query Time
60
Query Time
30.
15-
20-
10.
CANNAEAADCE SEALS Condsuttroppp ii DONG Sampling Methods
CANNESADGE StALS Condietentrgy
DCMG
CARAAEBAGGE seALs Condeetriiipy
is
Sampling Methods
Sampling Methods
(a) MNIST
(b) EMNIST
(c) SVHN
200
175
120
Query Time (5)
Time 150
130
125
Query Time
00
100
168
26
GANONEDADGE SEALS Conferinnnsy 8s D01G Sampling Methods
GAMAEEeNdE SEALE CansSers As DONG
GANVAS BROGs SEALS Condeetinncyy AS DGNS Sampling Methods
Samp ing Methods
(d) CIFAR10
(e) CIFAR100
(1) Mini ImageNet
Figure 7: Query time for 6 benchmarks and DGMG, averaged over fixed number of rounds for each method. The average time is averaged over repetitions for each experiment.
experimentation using static pro-computed data representation with the KNN critcrion, and its effect the overall accuracy and query time of the methods. It also provides a view of the different versions of DGAL (DGMG and DGLC) and the advantage of the DGAL latent diffusion methodology over other restriction criteria. particular, the comparison between VAE-SEALS and DGAL versions shows that DGAL is faster and achieves better accuracy. As seen in Figs. g DGMG has better accuracy than DGLC in most data sets.
11

---

Published in Transactions on Machine Learning Research (07/2024)
In Figure 8 DGAL versions have advantage over the VAF-SEATS. The VAR-SEALS can achieve similar accuracy with EMNIST, SVHN, CIFAR1O, and Mini-ImageNet but uses more time than DGAL in these cases. shows that the diffusion graph on latent space is more pow- erful than simply applying KNN on latent space. On the other data sets SEALS doesn't achieve the accuracy that DGAL achieves within the same range of queries.
Algorithm 3 The VAE-SEALS strategy
Input: Labeled data D1, unlabeled pool Du. the initial VAE model g, the task model [o, batch size B, round R, query strategy Q, label y train 9 with Dj implement the k-nearest neighbors structure ((s on the latent space g(D) = initialize the limited unlabeled pool as Dn =
for r (, do
active sub-sampling of batch B from Dy with criterion Q and network fo: DQ Q(fo, annotate DQ
Comparing DGLC with VAE-SEALS in Fig- ure 10 we observe the importance of pre- selection. The pro-sclection of SEALS lacks di- versity in the finst few rounds of data acquisition. Under the same sub-sampling method (the least confidence sampling) after pro-selcction, DGLC has an obvious advantage over VAE-SEALS at the beginning of the active learning cycles, especially for MNIST, EMNIST, CIFAR1O, and CIFAR100.
update Dj Di Dq. Da (Dn DQ) P2) UN(o, train fo with Dr
end for
In Figure 11 we observe that our methods (DGMG, DGLC) win over the others average query time. Due to the nature of the restriction process, all methods reduce the query time due a smaller pool set. Nevertheless,
in Figures and 10 while VAE-SEALS average query time may be similar to DGAL's, its accuracy trade-off with the query time is significantly worse than DGALs.
Total Query Time (5)
12
DOLC DONG
350
DGLC
WEGSALS
RS
Total Query Time (5)
120
VIESSALS
DELL
10.
100-
250
80
Total Query
6-
60
330
50
20
40
60
60
20
40
50
20
30
40
50
60
70
80
Test Accuracy (%)
Test Accuracy (1)
Test Accuracy 1%))
(a) MNIST
(b) EMNIST
(c) SVHN
Total Query Time (s)
400
DOLC
VAESDALS
250
96
DGLC DONG
VESSALS
Total Query Time (S)
2000
DGLC DXNS
VAESCALS
Total Query Time
300
50
30
40
50
60
70
80
10
20
30
40
50
70
20
30
40
50
60
70
80
90
Test Accuracy (%)
Test Accuracy (9)
Test Accuracy (%)
(d) CIFARIO
(6) CIFAR100
(f) Mini ImageNet
Figure& Test accuracy vs. total query time for VAE-SEALS, DGMG, DGLC, and Random (RS). The horizontal lines capture the highest and lowest test accuracy among all methods.
5.4 Ablation study
We conducted several ablation studics to investigate further on DGAL. First, we compare DGMG vs. non- DG-based confidence methods. The results show that the diffusion-based pre-selection contributes to a fast model improvement, especially in the early stage of querying. We also perform study in which substitute
12

---

Published in Transactions on Machine Learning Research (07 (07/2024)
various deep AL methods after diffusion-based restriction of the candidate set in Figure 14 Methods combined with the VAE diffusion method are laster than running them alone. Due to space limitation, we provide plotted results in Appendix
5.5 Results on ImageNet data
The ImageNet Deng et al. 2009) is well-known large-scale datasct in computer vision. It has approximately 1.3 million images with 1000 classes and average size of 469 387 pixels per image. Due to the size of the data set, many AL algorithms did not finish execution in reasonable time. We therefore present in Figure 9 the results of selected AL methods as well as the DGMG. As observed, DGMG achieves better accuracy than VAE-SEALS and Random sampling. In these multi-class problems, the accuracy difference is significant. We run the experiment with a query size 1000, and restriction to 20,000 in total query labels with 10, 7
55
RS
DGME
DONG WALSEALS
Total Query Time (s)
200000
Entropy
VAESEALS
Test Accuracy (%))
Entrpyy
LC
40
150000
100000
25
20-
20
25
35
50
2500 5000 75001060125005000 7502000022000000000000000
Test Accuracy (%)
Number of Labels
(a) Query time accuracy
(b) Accuracy number of labels
Figure 9: Experiments the ImageNet data.
6 Conclusion
We proposed diffusion-based sub-sampling method DGAL for efficient active learning. Unlike most active learning methods that feed the entire candidate pool set into the task model at each round, we first apply diffusion model for pre-selection of the query set and then apply a deep active learning criterion on the subset for final label acquisition. Our method outperforms others in both test accuracy and query time various experimental scttings and diverse data sets. We show an order of magnitude accelcration in the query time compared to all other benchmarks. the future, we plan to explore unsupervised representation learning schemes for improving latent space where label diffusion can be more efficiently applied.
References
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alckh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. arXiv preprint arXiv: 190600966,, 2019a.
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Project.
httpg/thh....mm//aa//aa///a//aaa 2019b.
J. Louis Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509 517, 1975.
Zalán Bod6, Zsolt Minier, and Lehel Csató. Active learning with clustoring. In Active Learning and Experimental Design workshop In conjunction with AISTATS 2010, volume 16 of Proceedings of Machine Learning Research, pp. 127-139, Sardinia, Italy, 16 May 2011.
13

---

Published in Transactions on Machine Learning Research (07/2024)
Joan Bruna and Stéphane Mallat. Invariant scattering convolution networks. JEEE transactions pattern analysis and machine intelligence, 35(8):1872 11866 2013.
Jeff Calder, Brendan Cook, Matthew Thorpe, and Dejan Slepcev. Poisson learning: Graph based semi-
supervised learning at very low label rates. In International Conference on Machine Learning, pp. 1306-1316. PMLR, 2020.
Olivier Chapelle, Bernhard Scholkopf, and Alexander Zien. Semi-supervised learning (chapelle, o. et al., eds.; 2006)[book reviews). IEEE Transaclions on Neural Networks, 20(3):542-55 -424222 2009.
Gregory Cohen, Saced Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist handwritten letters. In 2017 international joint conference neural networks (IJCNN), pp. 2921-2926.
IEEE, 2017.
Cody Coleman, Christopher Ych, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. arXíc preprint Xix::19006. 1 1189, 2019.
Cody Coleman, Edward Chou, Julian Katz-Sarnuls, Sean Culatana, Peter Bailis, Alexander C Berg, Robert Nowak, Roshan Sumbaly, Matei Zaharia, and 1 Zeki Yalniz. Similarity search for efficient active learning and search of rare concepts. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6402-6410, 2022a.
Cody Coleman, Edward Chou, Julian Kalz-Samuels, Sean Culatana, Peter Bailis, Alexander C Berg, Robert Nowak, Roshan Sumbaly, Matei Zaharia, and Zeki Yalniz. Project. httpp://giituub.comm// -text] 2022b.
Sanjoy Dasgupta. Two faces of active learning. Theoretical computer science, 412(19):1767 1781, 2011.
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. Locality-sensitive hashing scheme based p-stable distributions. In Proceedings of the twentieth annual symposium Compulational geomelry, pp. 253-262 2004.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pottern recognition, pp. 248 255. leee, 2009.
Carl Doersch. Tutorial on variational autoencoders. or Xiv preprint arXiv:1606.05908, 2016.
Alexcy Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image worth 16x16 words: Transformers for image recognition at scale. arXiv preprint 2xXi:22100111220 2020.
John Doucette and Malcolm I Heywood. Gp classification under imbalanced data sets: Active sub-sampling and aue approximation. In Genetic Programming: 11th European Conference, EuroGP 2008, Naples, Italy, March 26-28, 2008. Proceedings 11, pp. 266 277. Springer, 2008.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. Xiv preprint or Niw:1882.009.. 2018.
Seyda Ertekin, Jian Huang, Leon Bottou, and Lee Giles. Learning on the border: active learning in imbalanced data classification. Tn Proceedings of the sizteenth, ACM conference on Conference on information and knowledge management, pp. 127 136, 2007.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In International Conference on Machine Learning, pp. 1183 1192. PMLR, 2017.
Daniel Gissin and Shai Shwartz. Discriminative active learning. arXiv preprint orXiv:1907.066 063347, 2019.
14

---

Published in Transactions on Machine Learning Research (07/2024)
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEFE conference on computer vision and pollern recognition, pp. 770-778 2016.
Alex Holub, Pietro Perona, and Michael C Burl. Entropy-based active learning for object recognition. In 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, pp. 1-8. IEEE, 2008.
Miriam Huijser and Jan C van Gemert. Active decision boundary annotation with deep generative models. Proceedings of the IEEE international conference on compuler vision, pp. 5286 5295, 2017.
Jack Kiefer and Jacob Wolfowitz. Stochastic estimation of the maximum of regression function. The Annals of Mathematical Slatistics, pp. 462-466, 1952.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. ar preprinl orXiv:1412.6900 11800 2014.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114 2013.
Diederik P Kingma, Max Welling, et al. An introduction to variational autoencoders. Foundations and Trendsl in Machine Learning, 12(4):307 392, 2019.
Durk Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and Max Welling. Semi-supervised learning with deep generalive models. Advances in nearal information processing systems, 27, 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Dan Kushnir. Active-transductivee learning with label-adapted kernels. In 20th ACM SIGKDD international conference on Knowledge discovery and data mining,, volume 20, pp. 462 471, 2014.
Dan Kushmir and Luca Venturi. Diffusion-based sampling for deep active learning. In Fourteenth International Conference on Sampling Theory and Applications, 2023. URL. httpps://ppamerriieenttteffoorrs
]7QnDxW87FU
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 2324, 1998.
David Lewis. A sequential algorithm for training text classifiers: Corrigendun and additional data. Acm Sigir Forum, volume 29, pp. 13-19. ACM New York, NY, USA, 1995.
David D. Lewis and William A. Gale. A sequential algorithm for training text classifiers. In Proceedings of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '94, pp. 3 12, New York, NY, USA, 1994.
David G Lowe. Object recognition from local scale-invariant features. In Proceedings of the seventh IEEE international conference compuler vision, volume 2, pp. 1150 1157. leee, 1999.
Tong Luo, Kurt Kramer, Dmitry B Goldgof, Lawrence Hall, Scott Samson, Andrew Remsen, Thomas Hopkins, and David Cohn. Active learning recognize multiple types of plankton. Journal of Machine Learning Research, 6(4), 2005.
Katerina Margatina, Giorgos Vernikos, Loie Barrault, and Nikolaos Aletras. Active learning by acquiring contrastive examples. arXiv preprint Xrx::22109 003.666, 2021.
Christoph Mayer and Radu Timofte. Adversarial sampling for active learning. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 3071-3079, 2020.
Shaohui Mci, Jingyu Ji, Yunhao Geng, Zhi Zhang, Xu Li, and Qian Du. Unsupervisod spatial-spoctral feature learning by 3d convolutional autoencoder for hyperspectral classification. IEEE Transactions on Geoscience and Remole Sensing, 57(9))6808 08000,68800000 2019.
15

---

Published in Transactions on Machine Learning Research (07/2024)
Kevin Miller, Jack Mauro, Jason Setiadi, Xoaquin Baca, Zhan Shi, Jeff Calder, and Andrea L Bertozzi. Graph-based active learning for semi-supervised classification of sar data. In Algorithms for Synthetic Aperture Radar Imagery XXIX, volume 12095, pp. 126 139. SPIE, 2022.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits natural images with unsupervised feature learning. 2011.
S. M Omohundro. Five balltree construction algorithms. International Computer Science Institute Berkeley, 1989.
Amin Parvaneh, Ehsan Abbasnejad, Damien Teney, Gholamreza Reza Haffari, Anton van den Hengel, and Javen Qinfeng Shi. Active learning by feature mixing. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 12237 12246, 2022.
Farhad Pourkamali- Anaraaii and Michael B Wakin. The effectiveness of variational autoencoders for active lcarning. arXiv preprint arXiv:1911.0772 2019.
Sachin Ravi and Hugo Larochelle. Optimization model for few-shot learning. In International conference on learning representations, 2017.
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B. Gupta, Xiaojiang Chen, and Xin Wang. A survey of deep active learning. ACM Comput. Sure., 54(9), oct 2021.
P. Sparl S. Miklavic. baitaance-allaneed graphs. Discrete Applied Mathematics, 244:143 154, 2018.
Tobias SchefTer, Christian Decomain, and Stefan Wrobel. Active hidden markov models for information extraction. In International Symposium on Intelligent Data Analysis, pp. 309 318. Springer, 2001.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXie:1708. 00489, 2017a.
Ozan Sener and Silvio Savaresc. Project. [ttp:r//gttaa..cccccccaa///////t 9b.
Burr Settles. Active learning literature survey. 2009.
Dan Shen, Jie Zhang, Jian Su, Guodong Zhou, and Chew Lim Tan. Multi-criteria- based active learning for named entity recognition. In Proceedings of the 42nd annual meeting of the Associalion for Compulational Linguistics (ACL-04), pp. 589-596, 2004.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1cXic:1409.1550 2014.
Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational adversarial active learning. In Proceedings of the IEEE/CVF International Conference Compuler Vision, pp. 5972 5981, 2019a.
Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell. Project.
wwt../////..aaaaaaaa..aaaaaaaaaa 2019b.
Zixing Song, Xiangli Yang, Zenglin Xu, and Irwin King. Graph-based semi-supervised learning: A compre- hensive review. IEFE Transactions Neural Networks and Learning Systems, 2022.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. Tn International conference on machine learning, pp. 1139- 1147. PMLR, 2013.
Simon Tong and Daphne Koller. Support vector machinc active learning with applications to text classification. 2:45 66, 2001. URL
html
Yichen Xie, Masayoshi Tomizuka, and Wei Zhan. Towards general and efficient active learning. arXiv preprint Nii::2122.09960 2021.
16

---

Published in Transactions on Machine Learning Research (07/2024)
Donggeun Yoo and In So Kweon. Learning loss for active learning. In Proceedings of the IEEE/O /VF conference on computer vision and pallern. recognilion, pp. 93 93-102, 2019.
Michelle Yuan, Hsuan-Tien Lin, and Jordan Boyd-Graber Cold-start active learning through self-supervised language modeling. arXiv preprint ar arxiv:0000. 0rX0:22010.05555, 2020.
Zheng-Jun Zha, Tao Mei, Jingdong Wang, Zengfu Wang, and Xian-Sheng Hua. Graph-based semi-supervised learning with multiple labels. Journal of Visual Communication and Image Representation, 20(2):97 103, 2009.
Beichen Zhang, Liang Li, Shijie Yang, Shuhui Wang, Zheng-Jun Zha, and Qingming Huang. State-relabeling adversarial active learning. In Proceedings of the IEEE/CVF conference on computer vision and pollern recognition, pp. 8756-877 8765, 2020.
Jia-Jie Zhu and José Bento. Generative adversarial active learning. arXiv preprinl Xiv: 1702. 07956, 2017.
Jingbo Zhu, Huizhen Wang, Tianshun Yao, and Benjamin K Tsou. Active learning with sampling by uncertainty and density for word sense disambiguation and text classification. In Proceedings of the 22nd International Conference on Computational Lènguistics (Coling 2008), pp. 1137-1144, 2008.
Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), pp. 912-9112999 999, 2003.
Xiaojin Jerry Zhu. Semi-supervised learning literature survey. Technical report, University of Wisconsin- Madison Department of Computer Sciences, 2005.
17


Reviews:
[{"review_id": "5TzT6TKYKx", "reviewer": "Reviewer_AGA4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think the idea is pretty straightforward. Essentially, a pre-trained VAE is used for dimensionality reduction and then a sampling strategy that uses a graph diffusion process to propagate label information is applied.\n\n- The method seems to be empirically effective, although I still found the proposed method unnecessarily complicated. Whether the graph diffusion really necessary in unclear to me.\n\n- The method claims to address the intractability of large pool size, but the experiments also include datasets such as MNIST, CIFAR, Mini-imagenet. It is not very convincing to me that this method can really scale to millions of samples.\n\n- As a minor point, the improvement looks a bit marginal to me. For Figure 5, it could be better to use logarithm X-axis to show the improvement is really a magnitude of difference.\n\n- The ablation study does not well justify many of the design choices. Besides, hyperparameters should also be ablated. For example, different size of the neightborhood set should be tested.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new way to efficiently sample data points for active learning. Unlike past methods that need to scan over the entire dataset (hence intractable), the proposed method use a pre-trained VAE to restrict the size of the pool to a much smaller candidate set. This method demonstrates a better empirical efficiency.\n\nThe key contribution of this paper lies in the incorporation of the pre-trained VAE to embed raw data to a latent space, where a method caeed latent graph diffusion can be applied. The graph is computed by a similarity metric among the nearest neightborhood. Then a graph diffusion process is applied on this graph to propagate the label information.\n\nOverall, I think this paper introduces a simple graph-based sampling method to address the inefficiency of the label acquisition problem in active learning. Despite being a bit unnecessarily complicated, this method is able to demonstrate better efficiency over baselines.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Generally, I think the novelty of this method is incremental. But the novelty is not the primary focus of TMLR, so I will just focus on its claims.\n\n- The first claim that this method is scalable and efficient does not seem to hold with its current experiments (only CIFAR, MNIST and Mini-imagenet are used).\n\n- The speed-up is a magnitude better seems to hold. But Figure 5 should be modified to better reflect this claim.\n\nFor the other concerns, see the \"Strengths And Weaknesses\" section.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HvUlZUOQDC", "reviewer": "Reviewer_WaFV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\nThe empirical evaluation results presented in this paper indicate that the new method yields great acceleration on the querying action. The authors have also evaluated their method on multiple benchmarks to show that this acceleration is significant across several scenarios. Different ways of active learning are also tested and the proposed method seems to outperform existing methods on querying time and achieves similar performance.\n\t\n**Weaknesses:**\n\n1.\tThe use of VAE may make this method unable to scale to large-scale and high-resolution datasets. More specifically, how important is the representation quality of the pre-trained VAE for the good performance of the algorithm? The authors mainly evaluated their methods on datasets with low resolution (the highest resolution tested is 84 * 84). VAE will have worse representation quality for larger datasets with higher resolution, such as the full ImageNet. What performance curve will this method yield on this type of datasets?\n\n\n2.\tHow is the query time defined? I cannot find a definition for this important metric in the paper. Can the query time of other methods be reduced by applying methods like parallel computing?\n\n3.\tThe discussion or conclusion section is missing. The authors miss the opportunity to discuss potential limitations of their methods.\n\n4.\tThe writing needs to be improved. There are many typos in the paper, such as “bay be” instead of “may be” in the first paragraph of Sec. 4. Many sentences are also ungrammatical, such as missing “the” in some sentences.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work aims to improve the efficiency of deep active learning through utilizing the pre-trained VAE on the unlabeled data and an efficient query method on the hidden representations of the pre-trained VAE. This new method was compared to multiple earlier methods on several benchmarks. The authors show that their method (DGAL) outperforms existing methods on querying time while keeping a similarly high performance. They also provide ablation studies to support the design of their method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the weakness.", "broader_impact_concerns": "No clear negative society impacts from this.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vcSFYjKcAu", "reviewer": "Reviewer_zj16", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n----\n\n1. The query time has been improved compared to baselines. As the goal of this work, the proposed method shows superior performance. Figures 5 and 6 show that the proposed method shows improved query time, achieving better accuracy within a much shorter query time.\n2. This paper is well-organized, and according to the author's changes, the readability of this manuscript has been improved, including notations, definitions, equations, and discussion about VAE. \n3. Analysis for hyperparameters is provided in Section B. Graph diffusion methods are quite sensitive to hyperparameters. \n\nWeaknesses\n----\n\n1. Although the overall pipeline has been shown effective, technical contributions of this paper is quite limited. No new component. The ablation studies mainly compared the components brought from previous works in the literature. For instance, the uncertainty was measured by existing and straightforward ways after graph diffusion.\n2. Graph diffusion has been extensively studied in the literature. The authors used the existing concepts for semi-supervised learning. However, Graph Diffusion, or label smoothing on graphs are not a new concept. The authors should provide the related works graph diffusion for semi-supervised learning.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes an active learning method based on a deep generative model VAE with a Graph Diffusion Method, which is one of the main contributions of this paper is the overall pipeline that is a stack of existing methods. The authors provide detailed ablation studies replacing components. The effectiveness of the proposed method was verified by a better trade offs between query-time and accuracy.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. As mentioned in the weakness section, graph diffusion, and graph-based semi-supervised learning have been extensively studied in the literature. The authors need to compare the proposed method with existing methods regarding not only performance but also their pipelines to show the novelty of the proposed method in this paper. The role of generative modes, e.g., VAE, in this work is nothing but similarity computation, and it is not clear why the proposed method is computationally faster than other methods. All the graph-diffusion-based methods that use efficient matrix multiplication will have similar advantages since they have a short execution time per iteration. Figure 5 shows nothing but the proposed method. As shown in Figure 9 in the appendix, the proposed method does not show a relatively smaller improvement (not order of magnitude) with respect to the number of labels.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Some concerns were initially raised about the empirical support for the claims regarding improved scalability on large scale datasets. During the review process, the authors added experiments on ImageNet that demonstrate the evidence still holds in the large scale setting. The reviewers were generally satisfied by this additional evidence.

The authors are encouraged to move relevant details about the time complexity (Appendix B) and the ImageNet results (Appendix E.5) to the main paper as these are important pieces of evidence supporting the claims of the paper. Additionally, there are some remaining (minor) formatting and grammar issues that should be corrected.
Decision: Accept (poster)