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.

这篇论文以图论为基础，提出了开放世界半监督学习的理论框架，并在此基础上设计了一种叫做 “光谱开放世界表示学习” 的算法，用于从已标记数据中推断出未知类别的未标记数据，并且能在已知和未知类别的聚类任务中提供可靠的理论保证。