# A Graph-Theoretic Framework for Understanding Open-World Semi-Supervised Learning

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 86 references that are in the map.
- First posted on arXiv 6 Nov 2023.

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

- [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)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Momentum Contrast for Unsupervised Visual Representation Learning](https://mlsanity.com/paper/1911.05722/) (2019)
- [Exploring Simple Siamese Representation Learning](https://mlsanity.com/paper/2011.10566/) (2020)
- [Unsupervised Learning of Visual Features by Contrasting Cluster Assignments](https://mlsanity.com/paper/2006.09882/) (2020)
- [Supervised Contrastive Learning](https://mlsanity.com/paper/2004.11362/) (2020)
- [FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence](https://mlsanity.com/paper/2001.07685/) (2020)
- [Barlow Twins: Self-Supervised Learning via Redundancy Reduction](https://mlsanity.com/paper/2103.03230/) (2021)
- [CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning](https://mlsanity.com/paper/1612.06890/) (2016)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [Temporal Ensembling for Semi-Supervised Learning](https://mlsanity.com/paper/1610.02242/) (2016)
- [VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning](https://mlsanity.com/paper/2105.04906/) (2021)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Regularization With Stochastic Transformations and Perturbations for Deep Semi-Supervised Learning](https://mlsanity.com/paper/1606.04586/) (2016)
- [S4L: Self-Supervised Semi-Supervised Learning](https://mlsanity.com/paper/1905.03670/) (2019)
- [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)
- [Generalized Category Discovery](https://mlsanity.com/paper/2201.02609/) (2022)
- [OpenOOD v1.5: Enhanced Benchmark for Out-of-Distribution Detection](https://mlsanity.com/paper/2306.09301/) (2023)
- [Open-World Semi-Supervised Learning](https://mlsanity.com/paper/2102.03526/) (2021)
- [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)
- [Non-Parametric Outlier Synthesis](https://mlsanity.com/paper/2303.02966/) (2023)
- [Learning to cluster in order to transfer across domains and tasks](https://mlsanity.com/paper/1711.10125/) (2017)
- [Neighborhood Contrastive Learning for Novel Class Discovery](https://mlsanity.com/paper/2106.10731/) (2021)
- [Conditional Gaussian Distribution Learning for Open Set Recognition](https://mlsanity.com/paper/2003.08823/) (2020)
- [Novel Visual Category Discovery with Dual Ranking Statistics and Mutual Knowledge Distillation](https://mlsanity.com/paper/2107.03358/) (2021)

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

- [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)
- [Towards Few-Shot Adaptation of Foundation Models via Multitask Finetuning](https://mlsanity.com/paper/2402.15017/) (2024)
- [HiLo: A Learning Framework for Generalized Category Discovery Robust to Domain Shifts](https://mlsanity.com/paper/2408.04591/) (2024)
- [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)
- [DFA-RAG: Conversational Semantic Router for Large Language Model with Definite Finite Automaton](https://mlsanity.com/paper/2402.04411/) (2024)
- [Deep Active Learning in the Open World](https://mlsanity.com/paper/2411.06353/) (2024)
- [DATA: Multi-Disentanglement based Contrastive Learning for Open-World Semi-Supervised Deepfake Attribution](https://mlsanity.com/paper/2505.04384/) (2025)
- [Category Discovery: An Open-World Perspective](https://mlsanity.com/paper/2509.22542/) (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)
- [Re-Evaluating the Impact of Unseen-Class Unlabeled Data on Semi-Supervised Learning Model](https://mlsanity.com/paper/2503.00884/) (2025)
- [AdaptGCD: Multi-Expert Adapter Tuning for Generalized Category Discovery](https://mlsanity.com/paper/2410.21705/) (2024)
- [An Inclusive Theoretical Framework of Robust Supervised Contrastive Loss against Label Noise](https://mlsanity.com/paper/2501.01130/) (2025)
- [Urban Representation Learning for Fine-grained Economic Mapping: A Semi-supervised Graph-based Approach](https://mlsanity.com/paper/2505.11645/) (2025)
- [Weakly-Supervised Contrastive Learning for Imprecise Class Labels](https://mlsanity.com/paper/2505.22028/) (2025)
- [Sparsity Hurts: Simple Linear Adapter Can Boost Generalized Category Discovery](https://mlsanity.com/paper/2605.08183/) (2026)
- [ViTNF: Leveraging Neural Fields to Boost Vision Transformers in Generalized Category Discovery](https://mlsanity.com/paper/2506.02367/) (2025)
- [Information Theory in Open-world Machine Learning Foundations, Frameworks, and Future Direction](https://mlsanity.com/paper/2510.15422/) (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)

Open-world semi-supervised learning aims at inferring both known and novel classes in unlabeled data, by harnessing prior knowledge from a labeled set with known classes. Despite its importance, there is a lack of theoretical foundations for this problem. This paper bridges the gap by formalizing a graph-theoretic framework tailored for the open-world setting, where the clustering can be theoretically characterized by graph factorization. Our graph-theoretic framework illuminates practical algorithms and provides guarantees. In particular, based on our graph formulation, we apply the algorithm called Spectral Open-world Representation Learning (SORL), and show that minimizing our loss is equivalent to performing spectral decomposition on the graph. Such equivalence allows us to derive a provable error bound on the clustering performance for both known and novel classes, and analyze rigorously when labeled data helps. Empirically, SORL can match or outperform several strong baselines on common benchmark datasets, which is appealing for practical usage while enjoying theoretical guarantees.