Towards On-the-Fly Novel Category Discovery in Dynamic Long-Tailed Distributions

Hoin Jung, Xiaoqian WangWACV 2025 · OpenReview

Abstract: As the diversity of real-world object categories increases, the need for sophisticated classification methods also grows. However, Novel Category Discovery (NCD), which aims to predict unseen categories, often falls short in scenarios where new categories are constantly updated and data distributions are potentially biased. In addition, existing dynamic NCD approaches assume that incremental stages introduce a fixed number of new classes and often overlook distributional biases in real-world classes. To address these limitations, we propose a novel framework, Novel Category Discovery for Dynamic Long-Tailed distribution (NCD-DLT), which deals with the more realistic and challenging scenario where imbalanced, unlabeled data are introduced incrementally and sporadically over time. Unlike conventional methods requiring k-means clustering on all test samples, our approach identifies novel categories on-the-fly, predicting categories for individual data points as they arrive. We propose an advanced hash-based clustering technique, leveraging a double-hashing strategy to mitigate collisions and incorporating a greedy hash regularization loss for sparse representations to enhance clustering capabilities. Furthermore, we implement distillation losses during training to preserve the model's discriminative power across stages without forgetting prior knowledge. Finally, we introduce a novel graph merging algorithm based on the Hash Hamming Graph, revealing the dataset's clustering structure. It serves as a mechanism for pseudo-labeling in training and acts as a post-processing tool, reallocating less confident samples to more appropriate clusters. Our comprehensive approach addresses the limitations of existing NCD methods in the dynamic scenario of novel category discovery in long-tailed distributions, demonstrating improved accuracy for both uniform and long-tailed scenarios.

Introduction

Traditional Novel Category Discovery (NCD) algorithms typically operate under "laboratory conditions," assuming that data is balanced (uniform distribution) and that all unlabeled data arrives in a single batch. Furthermore, these methods often require a predefined number of expected new classes ($k$) or rely on computationally expensive searches to estimate it.

In real-world applications such as e-commerce or autonomous driving, data is inherently long-tailed—where a few categories are common while many are rare—and dynamic, with new categories appearing sporadically over time. Existing NCD methods struggle in these environments due to catastrophic forgetting, a dependency on batch-processing (which prevents real-time inference), and a distributional bias that often leads models to misidentify rare "tail" classes as noise.

The NCD-DLT Framework

To address these challenges, the NCD-DLT framework introduces a paradigm shift from batch-based clustering to on-the-fly discovery. The architecture is built upon three core technical pillars designed to handle the unpredictability of streaming data.

Double-Hashing and Sparse Representation

Instead of utilizing traditional $k$-means clustering, NCD-DLT maps images to binary hash codes. To prevent "collisions"—where distinct classes are assigned the same code—the model employs a double-hashing strategy combined with a greedy hash regularization loss. This approach forces the model to generate distinct, sparse representations for different objects, enabling inductive inference. This allows the model to classify a single incoming image instantly without requiring a batch of context images.

Figure 2: Overview of the dynamic training stage and the on-the-fly inference mechanism using hash-clustering.

Dual Distillation Losses

To mitigate catastrophic forgetting during incremental learning stages, the framework implements two forms of distillation:

  1. Static Distillation: Preserves foundational knowledge from the initial labeled "base" dataset.
  2. Dynamic Distillation: Ensures the model retains categories learned in the immediately preceding incremental step.

The Hash Hamming Graph (HHG)

The "brain" of the discovery process is the Hash Hamming Graph. In this graph, each node represents a unique hash code. Because long-tailed distributions often result in fragmented or low-confidence clusters, NCD-DLT utilizes a specialized Graph Merging Algorithm.

If a node is small or "unconfident" (indicated by hash bits hovering near 0.5), the algorithm reallocates those samples to more confident, neighboring clusters based on Hamming distance. This process effectively "cleans" the discovery results and allows the model to estimate the true number of classes automatically, rather than relying on a fixed $k$.

Figure 5: Visualization of the Hash Hamming Graph before and after the merging process, showing the reduction from 406 fragmented clusters to 108 cohesive ones.

Experimental Results

The framework was evaluated on long-tailed and incremental versions of CIFAR-10, CIFAR-100, and TinyImageNet. To simulate real-world imbalance, researchers applied imbalance ratios ($\rho$) of up to 100, where the most frequent class has 100x more samples than the rarest. Data was introduced across 20 incremental stages.

Key findings include:

  • Superior Accuracy: On uniform CIFAR-100, NCD-DLT achieved an "All" class accuracy of 59.66%, significantly outperforming the state-of-the-art OCD (51.05%).
  • Long-Tail Resilience: In the most challenging TinyImageNet scenario ($\rho=100$), NCD-DLT maintained stable performance while competing methods saw discovery accuracy for new classes drop sharply.
  • Class Estimation: The HHG proved highly effective at discovering the correct number of clusters. For instance, in CIFAR-100, while traditional binary search methods found only 74 clusters, the HHG identified 108—much closer to the ground truth of 100.

Conclusion

NCD-DLT represents a significant advancement toward deploying NCD in unconstrained environments. By replacing batch-dependency with hashing and graph-based merging, it provides a robust solution for real-time, long-tailed data streams. Future work will focus on refining hyperparameter sensitivity regarding hash code length and addressing the challenges of discovering categories from extremely scarce (one or two) samples.

Summary updated

Abstract

As the diversity of real-world object categories increases, the need for sophisticated classification methods also grows. However, Novel Category Discovery (NCD), which aims to predict unseen categories, often falls short in scenarios where new categories are constantly updated and data distributions are potentially biased. In addition, existing dynamic NCD approaches assume that incremental stages introduce a fixed number of new classes and often overlook distributional biases in real-world classes. To address these limitations, we propose a novel framework, Novel Category Discovery for Dynamic Long-Tailed distribution (NCD-DLT), which deals with the more realistic and challenging scenario where imbalanced, unlabeled data are introduced incrementally and sporadically over time. Unlike conventional methods requiring k-means clustering on all test samples, our approach identifies novel categories on-the-fly, predicting categories for individual data points as they arrive. We propose an advanced hash-based clustering technique, leveraging a double-hashing strategy to mitigate collisions and incorporating a greedy hash regularization loss for sparse representations to enhance clustering capabilities. Furthermore, we implement distillation losses during training to preserve the model's discriminative power across stages without forgetting prior knowledge. Finally, we introduce a novel graph merging algorithm based on the Hash Hamming Graph, revealing the dataset's clustering structure. It serves as a mechanism for pseudo-labeling in training and acts as a post-processing tool, reallocating less confident samples to more appropriate clusters. Our comprehensive approach addresses the limitations of existing NCD methods in the dynamic scenario of novel category discovery in long-tailed distributions, demonstrating improved accuracy for both uniform and long-tailed scenarios.
BibTeX
@inproceedings{jung2025towards,
  author = {Hoin Jung and Xiaoqian Wang},
  title = {{Towards On-the-Fly Novel Category Discovery in Dynamic Long-Tailed Distributions}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2025},
  url = {https://openreview.net/forum?id=DGtKS4ulLy},
}
Figure