nucleation

LIT-235: When and How Does Known Class Help Discover Unknown Ones? Provable Understanding Through Spectral Analysis

2 min read

Properties5
StatusActive — read 2026-10-14 (NOTE-833) in full; worth reading as an exact account, within HaoChen et al.'s spectral contrastive framework, of how labelled data from other classes changes which partition of unlabelled data the learned features express: the novel labelling's residual is its part outside the top eigenspace that the labelled rows of the discarded eigenvectors cannot absorb, and a toy shows known classes can help or hurt. Read it knowing that Theorem 5.5 is printed as ≤ though its proof gives equality, that everything is at the exact optimum of a population graph, that the general bound (Theorem 5.6) is approximate, pools all known classes into one averaged block and has notational slips, and that the help-or-harm examples have one sample per kind.
Version2
Tagsrepresentation-learning, learning-theory, anthology-candidate
Cited as “paper” byNOTE-208 — Sun et al. 2023 — spectral theory of novel class discovery, NOTE-833 — Sun, Shi, Liang & Li — when known classes help discover novel ones
Cited as “source” byTHEORY-320 — In a spectral contrastive graph that joins labelled known classes to unlabelled data, a novel labelling's linear-probe residual is exactly its part outside the top eigenspace that the labelled rows of the discarded eigenvectors cannot absorb, so which partition of the unlabelled data is discovered depends on the known classes: ones sharing the target's attribute can remove the residual, and ones sharing a rival attribute can raise it, THEORY-737 — In a spectral contrastive graph that joins labelled known classes to unlabelled data, the least-squares residual of a novel labelling on the top-k eigenspace, with the labelled entries left free, equals exactly the part of the labelling outside that eigenspace that the labelled rows of the discarded eigenvectors cannot absorb

Graph View

Yiyou Sun, Zhenmei Shi, Yingyu Liang, Yixuan Li (2023), Proceedings of the 40th International Conference on Machine Learning (ICML 2023), PMLR 202:33014–33043 — ARXIV-2308.05017

Key takeaways

From the reading, NOTE-833.

  • The graph. Vertices are augmented views. Edges join views of one unlabelled image and views of two labelled samples of the same known class. Known and novel data meet only through shared views. The rank-k factorization of the normalized adjacency is the optimum of a contrastive loss with five terms (Theorem 4.1).
  • The residual, exactly. Split the eigenvectors into kept (top k) and discarded, and each into labelled and unlabelled rows. A novel labelling y then has residual R = ‖(I − P_{L♭})U♭ᵀy‖² (Theorem 5.5, printed as ≤, proved as = in C.1). The 0–1 linear-probe error is at most 2R.
  • Help and harm (toy, §5.2). Unlabelled red and blue cubes and spheres, with shape linked more strongly than colour. A known red cylinder makes “red” recoverable (R = 0). A known gray cylinder leaves R = 1. A known gray cube makes it worse still (Lemma 5.4).
  • The general bound is approximate. Theorem 5.6 bounds the error by the “ignorance degree” times one minus squared “coverage”, plus ‖Ȧ − Ā‖₂/(σ_k − σ_{k+1}). Ā averages all labelled rows, so known classes act as one block. The quantities are not estimated on data.
  • Experiments. ResNet-18 on CIFAR: 64.0% novel clustering accuracy on CIFAR-100-50 against 53.4% for the best baseline, without error bars.

Standing in the record

Filed on 2026-09-26 at the owner’s request, from a list they grouped under the heading Representation learning as a spectral approximation, and read in full on 2026-10-14 in NOTE-833. It is held as an extension of HaoChen et al. (LIT-249, THEORY-228) to graphs that mix labelled and unlabelled data. Its residual identity and help-or-harm toy are filed as THEORY-320. That account bears on QUESTION-052: the partition a spectrum expresses depends on what else the operator connects. It also gives a formal instance of CLAIM-152.

Tagged anthology-candidate (ADR-005): NSCL as a method for novel class discovery is machine-learning practice. The residual analysis is learning theory of the kind this record holds. It is kept here by the owner’s decision of 2026-09-26 that new work stays in nucleation until a transfer is judged appropriate (ADR-010).

Backlinks