Timezone: »

When and How Does Known Class Help Discover Unknown Ones? Provable Understanding Through Spectral Analysis
Yiyou Sun · Zhenmei Shi · Yingyiu Liang · Sharon Li

Wed Jul 26 02:00 PM -- 03:30 PM (PDT) @ Exhibit Hall 1 #120

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.

Author Information

Yiyou Sun (University of Wisconsin Madison)
Zhenmei Shi (UW-Madison)
Yingyiu Liang (University of Wisconsin-Madison)
Sharon Li (University of Wisconsin-Madison)

More from the Same Authors