Semi-supervised graph propagation and pseudo-labeling limits — Examples

Take $\mathcal{X}=\{0,1,2,3,4,5\}$ with distance $d(x,y)=\mathrm{\mid }x-y\mathrm{\mid }$ and classes $\{1,2\}$. The true labels at $0,1,2,3,4,5$ are $1,1,1,1,2,2$, but only the examples $(0,1),(1,1),(2,1),(3,1),(4,2)$ are labeled for the procedure. Run the finite confidence-threshold pseudo-labeling algorithm with unlabeled set $\{5\}$, $k=5$, threshold $\tau =4\mathrm{/}5$, pseudo-label weight $\lambda =1$, and round cap $T=1$. The nearest labeled examples to $5$ have labels $2,1,1,1,1$, so confidence $4\mathrm{/}5$ assigns the wrong label $1$; the no-relabel rule retains that assignment.

The nodes lie at their feature coordinates on the real line. Labels after a colon are observed labels for positions 0 through 4; the question mark at 5 is unlabeled to the algorithm. The hidden true class at 5 is 2. The drawn line shows distance order only, not a graph edge set.

diagram failed to render:
\begin{tikzpicture}
\node[draw,circle] (x0) at (0,0) {$0:1$};
\node[draw,circle] (x1) at (1.5,0) {$1:1$};
\node[draw,circle] (x2) at (3,0) {$2:1$};
\node[draw,circle] (x3) at (4.5,0) {$3:1$};
\node[draw,circle] (x4) at (6,0) {$4:2$};
\node[draw,circle,dashed] (x5) at (7.5,0) {$5:?$};
\draw (x0)--(x1)--(x2)--(x3)--(x4)--(x5);
\node at (7.5,-0.75) {true class 2};
\end{tikzpicture}

Let $\mathcal{X}=\{a,b\}$ with the discrete sigma-algebra and feature marginal $P_X(a)=P_X(b)=1\mathrm{/}2$, and observe only the labeled pair $(a,0)$. Under $P_0$, the labels at $a,b$ are $0,0$; under $P_1$, they are $0,1$. The common learner input consists of this labeled pair and the full marginal $P_X$. Let $\mathcal{H}=\{g:\mathcal{X}\to \{0,1\}\}$, and let $Q:\mathcal{H}\to [0,1]$ satisfy ${\sum }_{g\in \mathcal{H}}Q(g)=1$, selected from that common input, so it is the same under both laws. For $g\in \mathcal{H}$, define $R_{P_0}(g)=\frac{1}{2}\mathbf{1}\{g(a)\mathrm{\ne }0\}+\frac{1}{2}\mathbf{1}\{g(b)\mathrm{\ne }0\},R_{P_1}(g)=\frac{1}{2}\mathbf{1}\{g(a)\mathrm{\ne }0\}+\frac{1}{2}\mathbf{1}\{g(b)\mathrm{\ne }1\}\mathrm{.}$ The expected population risks satisfy ${\max }_{j\in \{0,1\}}{\sum }_{g\in \mathcal{H}}Q(g)R_{P_j}(g)\ge 1\mathrm{/}4$.

Each panel gives feature, label, and mass. The input at $a$ is observed in both panels; the feature masses agree, while only the unobserved label at $b$ changes.

diagram failed to render:
\begin{tikzpicture}
\draw (0,0) rectangle (3.5,1.8);
\node at (1.75,1.45) {$P_0$};
\node at (0.9,0.9) {$a:0$};
\node at (2.6,0.9) {$b:0$};
\node at (0.9,0.35) {$1/2$};
\node at (2.6,0.35) {$1/2$};
\draw (4,0) rectangle (7.5,1.8);
\node at (5.75,1.45) {$P_1$};
\node at (4.9,0.9) {$a:0$};
\node at (6.6,0.9) {$b:1$};
\node at (4.9,0.35) {$1/2$};
\node at (6.6,0.35) {$1/2$};
\end{tikzpicture}

Take the path with vertices $1,2,3$, unit weights on edges $\{1,2\}$ and $\{2,3\}$, labeled boundary $B=\{1,3\}$, and values $y_1=0$, $y_3=1$. The unique graph-harmonic extension assigns value $1\mathrm{/}2$ to vertex 2 and has Dirichlet energy $1\mathrm{/}4$.

The labels inside the end vertices are their prescribed boundary values. Each drawn undirected edge has weight 1; vertex 2 is unlabeled. The calculation in Verification uses the energy formula, not the drawing.

diagram failed to render:
\begin{tikzpicture}
\node[draw,circle] (v1) at (0,0) {$1:0$};
\node[draw,circle] (v2) at (2,0) {$2$};
\node[draw,circle] (v3) at (4,0) {$3:1$};
\draw (v1)--node[above] {$1$}(v2);
\draw (v2)--node[above] {$1$}(v3);
\end{tikzpicture}

Let $V=\{1,2,3\}$, with the single unit-weight edge $\{1,2\}$, labeled set $B=\{1\}$, boundary value $y_1=0$, and unlabeled set $U=\{2,3\}$. The isolated component $\{3\}$ contains no labeled vertex, so the graph-harmonic propagation algorithm returns status $\mathtt{\text{unanchored-component}}$ before forming a linear solve.

The edge between 1 and 2 has weight 1; vertex 1 has boundary value 0. Vertices 2 and 3 are unlabeled, and vertex 3 is isolated. The verification checks the support components directly.

diagram failed to render:
\begin{tikzpicture}
\node[draw,circle] (v1) at (0,0) {$1:0$};
\node[draw,circle] (v2) at (2,0) {$2$};
\node[draw,circle] (v3) at (4,0) {$3$};
\draw (v1)--node[above] {$1$}(v2);
\end{tikzpicture}