Where to Spend the Labels: Drift-Localized Active Learning on Decade-Long Streams

Security classifiers such as Android malware detectors decay as the software ecosystem changes. The standard remedy is active learning: each month an analyst labels a small, carefully chosen batch of new samples, and the model is retrained on them. On the 322,000-app APIGraph benchmark this works, reaching about 92% F1 with a 400-sample budget. On the 1,008,381-app, 12-year LAMDA benchmark, the same approach collapses to 43% F1 (LAMDA). We propose that the collapse is mainly a failure of where the labels go, not of the classifier. LAMDA contains 1,380 malware families and more than 150,000 singletons. A picker that ranks samples globally by uncertainty spends a small budget on a few confusing regions and leaves most drifting regions with labels that are years old.

Our fix is to keep a persistent tree over the input space whose nodes are regions that keep their identity from month to month. Each node records two things cheaply as samples arrive and leave: how much its recent inputs differ from what it held when it was last labeled, and how old its newest label is. The monthly budget is then split from the root down according to these two quantities, and retraining replays data in proportion to the same scores. The tree design borrows from dynamic algorithms that confine each change to a single path in a tree and limit how much the maintained structure changes per update. Those algorithms are what let per-region label histories stay meaningful over years of insertions and deletions.

Core Claim

Two claims can be tested separately. The diagnostic claim is that on LAMDA, existing active drift adaptation leaves most of the regions whose input distribution has shifted with no fresh labels, and that this starvation predicts where false negatives land. If that is false, the proposal is wrong and we stop. The constructive claim is that allocating the same budget by region-level input drift and label age, using regions that persist over time and exist at several scales, recovers a large part of the gap between 43% and 92% F1. We also claim this beats a flat, re-clustered-every-batch version of the same idea. That comparison is what shows the hierarchy and its persistence are doing the work.

Relation to Prior Work

Three lines of work motivate the gap. LAMDA documents the collapse but proposes no method. AnoShift shows a similar decade-long decay in network anomaly detection, where Local Outlier Factor falls from 91.50 to 34.96 ROC-AUC. It also finds that plain fine-tuning forgets old data, a constraint our replay design has to respect. The early stream study MOA Concept Drift Active Learning Strategies shows that pure uncertainty sampling cannot see drift away from the decision boundary; we treat this as the small-scale version of our starvation hypothesis.

The closest methods fall into three groups, and each lacks one piece.

  • Pseudo-loss selection. Continuous Learning for Android Malware Detection organizes its embedding by malware family through hierarchical contrastive learning and selects samples by a nearest-neighbor pseudo-loss. It has no persistent region structure and no notion of per-region label age. We reuse its encoder and its warm-start retraining, which it shows beats retraining from scratch, and replace only the selection step.
  • Per-batch clustering. ACLStream ranks K-Means clusters by how split the classifier's predictions are, and it is the strongest flat competitor. It re-clusters every batch, so no cluster exists long enough to carry a label history.
  • Drift-timed budgets. PRopagate with a drift-dependent budget raises the labeling rate globally when an unsupervised detector fires, and predicts pending labels by nearest neighbors weighted toward recent ones. It decides when to spend, whereas we decide where. It was also tested only with small classifiers on small streams.

The tree mechanics come from other work. IKS keeps a randomized search tree over a sliding window so that insertion, eviction and the Kolmogorov–Smirnov statistic are cheap. We embed tests of that kind at internal nodes instead of running one external detector. Dynamic clustering with bounded solution change (fully dynamic k-center with recourse, dynamic high-dimensional facility location) and single-path repair (Goranci et al.) supply the principle that an insertion should touch only one root-to-leaf path. They are analyzed against worst-case adversaries rather than drifting data, and we use them as design guidance, not as guarantees we inherit.

Flattening a Hierarchical Clustering through Active Learning queries labels to choose a cut through a fixed tree. We borrow the idea that the tree's shape should reduce query cost, but our tree changes over time and the "cut" is a budget allocation that is recomputed monthly.

One paper constrains the design. How Important is Importance Sampling for Deep Budgeted Training? finds that biased selection loses to uniform sampling plus augmentation under tight training budgets, because it removes variety from the training data. This is why every node keeps a floor share of the budget and the retraining replay is stratified by node.

Research Program

The tree. It is built on a fixed random projection of the static features, not on the learned embedding. That way, retraining the classifier does not move every point and destroy region identity. A learned-embedding tree, rebuilt each month, is an ablation. New apps descend to a leaf. Leaves split when they grow too large and merge when their counts fall. Each split or merge updates statistics only along one path to the root, and we log the number of nodes restructured per month as the empirical measure of how much the structure changes.

Per-node statistics. Each node $v$ stores a small reference sketch from when it was last labeled and a window of recent arrivals. From these it computes an input-drift score $s_v$, a two-sample statistic over the projected coordinates, with a classifier two-sample test (Lee) as the multivariate variant. It also tracks the label age $a_v$, the number of months since the node's newest label.

Budget allocation. The monthly budget $B$ is divided top-down. A child $c$ receives a share proportional to

$$w_c = n_c \,(s_c + \lambda\, a_c) + \epsilon\, n_c,$$

where $n_c$ is the child's recent arrival count, $\lambda$ trades drift against staleness, and $\epsilon$ is the floor that preserves coverage. Within a leaf, samples are chosen by the pseudo-loss of Continuous Learning. Because allocation happens at every level, drift at the level of a family and drift across a whole super-family are both handled at the scale where they occur.

Localized updates. Retraining warm-starts from the previous weights. The replay set is drawn node-stratified and upweights nodes with high $s_v$. This targets the forgetting reported in AnoShift.

Verification latency. Labels arrive with a configurable delay of 0, 1 or 3 months. Pending queries count toward $a_v$ as "in flight" so the allocator does not query the same region twice, which is the node-level analogue of the redundancy problem identified by PRopagate.

Baselines

No adaptation. The naive reference is LightGBM trained once on the IID years. LAMDA reports 97.49% F1 on IID, 59.48% on NEAR and 47.24% on FAR, with a false-negative rate of 64.10% on FAR. Uniform random selection at the same budget, with the same encoder and warm-start retraining, is the second naive point.

Strongest existing method. This is the active drift adaptation method benchmarked in LAMDA, which reports about 92% F1 on APIGraph and 43% F1 on LAMDA at a 400-sample budget. Alongside it we run the hierarchical-contrastive, pseudo-loss learner of Continuous Learning, which reports more than 89% average F1 on APIGraph at 50 samples per month. Both run on LAMDA's temporal splits with the same budget, the same Drebin-style features and the same retraining schedule, and all methods get the same hyperparameter search. Clearly beating the strongest method means exceeding 43% F1 on LAMDA's FAR years by a margin larger than the spread across seeds, while also lowering the false-negative rate. Closing half the gap to the APIGraph level would be a strong result.

Competitors. ACLStream runs with $k$ tuned over its reported insensitive range of 5 to 25. PRopagate with its drift-timed budget (Castellani et al.) is ported from its small classifiers to our encoder.

Ablations. Four ablations isolate what the method adds. A flat-persistent version keeps leaves with persistent identity but allocates without the hierarchy. A flat-reclustered version recomputes K-Means each month and uses the same $w$ scores. Two further versions drop the drift term or the staleness term.

Why not just…?

Why not just sample uniformly and augment? Budgeted training shows uniform sampling with augmentation beating biased selection on CIFAR-100: 76.27% at a 30% budget versus 75.44% at full budget. That was a stationary setting where labels were already available. Augmentation cannot create labels for a malware family that appears for the first time. The threat is still real, and the $\epsilon$ floor and the uniform baseline exist so that the experiment can show uniform sampling to be competitive if it is.

Why not just run ACLStream-style flat clustering with drift weights? This is the most dangerous alternative. If flat-reclustered allocation matches our method, then region persistence and hierarchy add nothing, and we would report exactly that. Our prediction is that it loses specifically under latency and on families that recur after years of absence. Both cases need a label history attached to a region, which per-batch clusters cannot keep. The flat-persistent ablation separates the value of persistence from the value of hierarchy.

Why not just raise the budget when a global detector fires, as PRopagate does? A detector that fires globally tells the learner that drift occurred but not where. Our diagnostic, described below, tests whether starvation is spatial. If LAMDA's drift is dominated by abrupt ecosystem-wide shifts, global timing may suffice, and the comparison would reveal it.

Why not just retrain periodically on a sliding window? A sliding window keeps only recent labels. That makes the model forget, as seen in AnoShift, and does nothing about the small budget being spent in the wrong places. We include window retraining at a matched labeling budget as a baseline.

Proposed Experiments

The first, decisive check is the diagnostic, run before building anything. For the LAMDA active learning baseline, we compute each month the fraction of samples falling in nodes with high drift and label age above 12 months. We then test whether false negatives concentrate in those nodes. If they do not, the starvation hypothesis fails.

The main experiment runs every method on LAMDA's NEAR and FAR splits. We report monthly F1 and false-negative rate, compare methods at budgets of 50, 100 and 400, and repeat under latencies of 0, 1 and 3 months. APIGraph checks that the method does not regress where the existing methods already work. AnoShift's Kyoto-2006+ stream, where anomaly labels are available, tests whether the effect transfers to a low-dimensional domain other than malware; no reported result found on Lacuna for an active learning method on AnoShift. The ACLStream streams (Electricity, Cover Type, Airlines) serve as a small-scale sanity check.

For computation, we report wall-clock time per month, nodes restructured per month, and time to compute per-node statistics, as a function of stream size up to the full one million apps. The scaling claim holds only if per-arrival cost stays roughly constant as the stream grows.