# When and How Does Known Class Help Discover Unknown Ones? Provable Understanding Through Spectral Analysis

arXiv: https://arxiv.org/abs/2308.05017 · HTML: https://mlsanity.com/paper/2308.05017/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 52 references that are in the map.
- First posted on arXiv 9 Aug 2023.

## Builds on (most cited first, 30 of 32)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Exploring Simple Siamese Representation Learning](https://mlsanity.com/paper/2011.10566/) (2020)
- [CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning](https://mlsanity.com/paper/1612.06890/) (2016)
- [Out-of-Distribution Detection with Deep Nearest Neighbors](https://mlsanity.com/paper/2204.06507/) (2022)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [ReAct: Out-of-distribution Detection With Rectified Activations](https://mlsanity.com/paper/2111.12797/) (2021)
- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [Learning to Discover Novel Visual Categories via Deep Transfer Clustering](https://mlsanity.com/paper/1908.09884/) (2019)
- [Delving into Out-of-Distribution Detection with Vision-Language Representations](https://mlsanity.com/paper/2211.13445/) (2022)
- [A Unified Objective for Novel Class Discovery](https://mlsanity.com/paper/2108.08536/) (2021)
- [Predicting What You Already Know Helps: Provable Self-Supervised Learning](https://mlsanity.com/paper/2008.01064/) (2020)
- [Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods](https://mlsanity.com/paper/2205.11508/) (2022)
- [Contrastive learning, multi-view redundancy, and linear models](https://mlsanity.com/paper/2008.10150/) (2020)
- [Automatically Discovering and Learning New Visual Categories with Ranking Statistics](https://mlsanity.com/paper/2002.05714/) (2020)
- [Learning to cluster in order to transfer across domains and tasks](https://mlsanity.com/paper/1711.10125/) (2017)
- [How to Exploit Hyperspherical Embeddings for Out-of-Distribution Detection?](https://mlsanity.com/paper/2203.04450/) (2022)
- [Neighborhood Contrastive Learning for Novel Class Discovery](https://mlsanity.com/paper/2106.10731/) (2021)
- [Novel Visual Category Discovery with Dual Ranking Statistics and Mutual Knowledge Distillation](https://mlsanity.com/paper/2107.03358/) (2021)
- [Multi-class Classification without Multi-class Labels](https://mlsanity.com/paper/1901.00544/) (2019)
- [SpectralNet: Spectral Clustering using Deep Neural Networks](https://mlsanity.com/paper/1801.01587/) (2018)
- [OpenMix: Reviving Known Knowledge for Discovering Novel Visual Categories in An Open World](https://mlsanity.com/paper/2004.05551/) (2020)
- [Supporting Clustering with Contrastive Learning](https://mlsanity.com/paper/2103.12953/) (2021)
- [Connect, Not Collapse: Explaining Contrastive Learning for Unsupervised Domain Adaptation](https://mlsanity.com/paper/2204.00570/) (2022)
- [Joint Representation Learning and Novel Category Discovery on Single- and Multi-modal Data](https://mlsanity.com/paper/2104.12673/) (2021)
- [Contrastive estimation reveals topic posterior information to linear models](https://mlsanity.com/paper/2003.02234/) (2020)
- [Beyond Separability: Analyzing the Linear Transferability of Contrastive Representations to Related Subpopulations](https://mlsanity.com/paper/2204.02683/) (2022)
- [OpenCon: Open-world Contrastive Learning](https://mlsanity.com/paper/2208.02764/) (2022)
- [Meta Discovery: Learning to Discover Novel Classes given Very Limited Data](https://mlsanity.com/paper/2102.04002/) (2021)

## Built on by (most cited first, 21 of 21)

- [ARGS: Alignment as Reward-Guided Search](https://mlsanity.com/paper/2402.01694/) (2024)
- [Process Reward Model with Q-Value Rankings](https://mlsanity.com/paper/2410.11287/) (2024)
- [Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalability](https://mlsanity.com/paper/2407.15720/) (2024)
- [Learn to Categorize or Categorize to Learn? Self-Coding for Generalized Category Discovery](https://mlsanity.com/paper/2310.19776/) (2023)
- [Diversified Outlier Exposure for Out-of-Distribution Detection via Informative Extrapolation](https://mlsanity.com/paper/2310.13923/) (2023)
- [Towards Few-Shot Adaptation of Foundation Models via Multitask Finetuning](https://mlsanity.com/paper/2402.15017/) (2024)
- [PointAD: Comprehending 3D Anomalies from Points and Pixels for Zero-shot 3D Anomaly Detection](https://mlsanity.com/paper/2410.00320/) (2024)
- [A Graph-Theoretic Framework for Understanding Open-World Semi-Supervised Learning](https://mlsanity.com/paper/2311.03524/) (2023)
- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [On the Learnability of Out-of-distribution Detection](https://mlsanity.com/paper/2404.04865/) (2024)
- [When and How Does In-Distribution Label Help Out-of-Distribution Detection?](https://mlsanity.com/paper/2405.18635/) (2024)
- [DFA-RAG: Conversational Semantic Router for Large Language Model with Definite Finite Automaton](https://mlsanity.com/paper/2402.04411/) (2024)
- [Category Discovery: An Open-World Perspective](https://mlsanity.com/paper/2509.22542/) (2025)
- [Open-World Deepfake Attribution via Confidence-Aware Asymmetric Learning](https://mlsanity.com/paper/2512.12667/) (2025)
- [Labeled Data Selection for Category Discovery](https://mlsanity.com/paper/2406.04898/) (2024)
- [Bridging OOD Detection and Generalization: A Graph-Theoretic View](https://mlsanity.com/paper/2409.18205/) (2024)
- [A Practical Approach to Novel Class Discovery in Tabular Data](https://mlsanity.com/paper/2311.05440/) (2023)
- [MCL-AD: Multimodal Collaboration Learning for Zero-Shot 3D Anomaly Detection](https://mlsanity.com/paper/2509.10282/) (2025)
- [Detecting and Learning Out-of-Distribution Data in the Open world: Algorithm and Theory](https://mlsanity.com/paper/2310.06221/) (2023)
- [PointAD+: Learning Hierarchical Representations for Zero-shot 3D Anomaly Detection](https://mlsanity.com/paper/2509.03277/) (2025)
- [The Devil Is in Gradient Entanglement: Energy-Aware Gradient Coordinator for Robust Generalized Category Discovery](https://mlsanity.com/paper/2604.14176/) (2026)

## Abstract (arXiv)

Novel Class Discovery (NCD) aims at inferring novel classes in an unlabeled set by leveraging prior knowledge from a labeled set with known classes. Despite its importance, there is a lack of theoretical foundations for NCD. This paper bridges the gap by providing an analytical framework to formalize and investigate when and how known classes can help discover novel classes. Tailored to the NCD problem, we introduce a graph-theoretic representation that can be learned by a novel NCD Spectral Contrastive Loss (NSCL). Minimizing this objective is equivalent to factorizing the graph's adjacency matrix, which allows us to derive a provable error bound and provide the sufficient and necessary condition for NCD. Empirically, NSCL can match or outperform several strong baselines on common benchmark datasets, which is appealing for practical usage while enjoying theoretical guarantees.