nucleation

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

2 min read

Properties4
StatusActive
Tagsrepresentation-learning, learning-theory
SourceLIT-235 — When and How Does Known Class Help Discover Unknown Ones? Provable Understanding Through Spectral Analysis
Extended 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

Graph View

Source

Sun, Shi, Liang & Li (2023), LIT-235, §4 (the graph, Eq. 1), §5.3 (Theorem 5.5) and appendix C.1, read in NOTE-833.

What was actually shown

The setting. Vertices are augmented views. Edges join views of labelled samples of one known class and views of one unlabelled image (Eq. 1). Let V = [F G] be an orthogonal matrix whose first k columns F are the top-k singular vectors of the normalized adjacency. Split the rows into labelled and unlabelled: F = [L*; U*] and G = [L♭; U♭]. For a novel labelling y of the unlabelled vertices, let the labelled entries of the target float:

R(U*, y) = min over w, z of ‖F w − [z; y]‖².

The identity, re-derived.

  1. For a fixed target t = [z; y], min_w ‖F w − t‖² = ‖(I − FFᵀ)t‖² = ‖Gᵀt‖², because F has orthonormal columns and FFᵀ + GGᵀ = I.
  2. Gᵀt = L♭ᵀz + U♭ᵀy.
  3. Minimizing ‖L♭ᵀz + U♭ᵀy‖² over z is least squares. Its value is ‖(I − P_{L♭})U♭ᵀy‖², where P_{L♭} = L♭ᵀ(L♭L♭ᵀ)†L♭ projects onto the range of L♭ᵀ.

So R(U*, y) = ‖(I − P_{L♭})U♭ᵀy‖², an equality. The residual is zero iff U♭ᵀy lies in the range of L♭ᵀ, that is, iff some ω has u_iᵀy = l_iᵀω for every discarded i. By the paper’s Lemma 5.1, the 0–1 linear-probe error on the unlabelled data is at most 2R.

What could have come out otherwise: the residual could have depended on the top-k rows of the labelled data, or have been only bounded by the projection. It is exactly the projection.

What this does not say

  • Nothing about trained networks. The identity holds at the exact rank-k factorization of the population graph.
  • Not the toy results. That a known class sharing the target’s attribute removes the residual, and that one sharing a rival attribute raises it, are THEORY-320’s claims. They rest on eigenvector computations in an appendix the record has not read.
  • Not Theorem 5.6. The paper’s approximate coverage bound is not part of this.

Connections

  • THEORY-320 extends this. It adds the paper’s toy demonstrations of help and harm, and keeps them Proposed.
  • THEORY-228 (HaoChen’s conductance bound) is the framework the graph comes from. This gives the residual exactly, through the discarded eigenvectors.

Backlinks