Label Propagation treats both labelled and unlabelled points as nodes in a weighted graph, where edge weights reflect similarity (RBF kernel). Labels are "spread" from labelled nodes to unlabelled neighbours iteratively, converging when the label distribution stabilises. It exploits the manifold assumption: nearby points in feature space likely share the same label.
Weight matrix (RBF kernel):
\[W_{ij} = \exp\!\left(-\frac{\|\mathbf{x}_i - \mathbf{x}_j\|^2}{2\sigma^2}\right)\]Let \(D\) be the diagonal degree matrix, \(D_{ii} = \sum_j W_{ij}\). The two methods use different normalisations of \(W\) — this is what separates them.
(a) Label Propagation — Zhu & Ghahramani (2002). Row-stochastic transition matrix, hard clamping:
\[\mathbf{T} = D^{-1}W, \qquad T_{ij} = \frac{W_{ij}}{\sum_k W_{ik}}\] \[F^{(t+1)} = T F^{(t)}, \quad \text{then reset } F^{(t+1)}_l = Y_l \ \ \forall\, l \in \mathcal{L}\]Labelled rows are clamped back to their known values after every sweep, so there is no \(\alpha\). Implemented by sklearn.semi_supervised.LabelPropagation.
(b) Label Spreading — Zhou et al. (2004). Symmetrically normalised affinity, soft clamping:
\[\mathcal{S} = D^{-1/2} W D^{-1/2}\] \[F^{(t+1)} = \alpha\, \mathcal{S}\, F^{(t)} + (1-\alpha) Y_0\]where \(Y_0\) holds the known labels (rows of zeros for unlabelled nodes) and \(\alpha \in (0,1)\) sets how far a label may travel before the original evidence pulls it back. Implemented by sklearn.semi_supervised.LabelSpreading.
Closed-form solution (Label Spreading):
\[F^* = (1-\alpha)\,(I - \alpha \mathcal{S})^{-1} Y_0\]The iteration converges because \(\alpha\,\mathcal{S}\) has spectral radius \(\alpha < 1\).
Label Propagation (hard clamping) and Label Spreading (soft clamping with \(\alpha\)) are two variants. Hard clamping holds labelled nodes fixed; soft clamping allows them to be influenced by neighbours (more robust to label noise). The graph structure captures the underlying data manifold, making label propagation effective even with very few labels (<1% of data). The RBF bandwidth \(\sigma\) and \(\alpha\) are tuned via cross-validation on the labelled subset.
In a transaction graph, a few known fraudulent accounts are labelled. Label propagation spreads the fraud signal to connected accounts via shared IP addresses and device IDs, flagging a fraud ring of 340 accounts from just 15 known fraudsters.
| Stage | Known Fraud | Flagged Total |
|---|---|---|
| Initial | 15 | 15 |
| After propagation | 15 | 340 |
A few confirmed infested fields are labelled. Label propagation through a spatial proximity graph identifies likely-infested neighbouring fields before visual symptoms appear, enabling pre-emptive pesticide application.
| Fields confirmed | Fields flagged | Precision |
|---|---|---|
| 12 | 68 | 0.76 |
A few patients with confirmed late-stage Parkinson's are labelled. Label propagation through a similarity graph of biomarker profiles identifies likely early-stage patients for inclusion in preventive treatment trials.
| Known late-stage | Early-stage flagged | Sensitivity |
|---|---|---|
| 25 | 112 | 0.81 |
import numpy as np
import pandas as pd
from sklearn.semi_supervised import LabelPropagation, LabelSpreading
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_report, accuracy_score
from sklearn.model_selection import train_test_split
np.random.seed(42)
N = 1000
# ── Simulate Patient Biomarker Data (Parkinson's staging) ─────
X_all = np.column_stack([
np.random.normal(0, 1, N), # Tremor score
np.random.normal(0, 1, N), # Dopamine level
np.random.normal(0, 1, N), # Gait asymmetry
])
# True labels: 0=early, 1=late
true_y = ((X_all[:,0] + X_all[:,2] - X_all[:,1]) > 0).astype(int)
X_tr, X_te, y_tr, y_te = train_test_split(X_all, true_y, test_size=0.2, random_state=42)
sc = StandardScaler()
X_tr_sc = sc.fit_transform(X_tr)
X_te_sc = sc.transform(X_te)
# ── Only 25 labelled samples ──────────────────────────────────
y_semi = -np.ones(len(y_tr), dtype=int) # -1 = unlabelled
labelled_idx = np.random.choice(len(y_tr), 25, replace=False)
y_semi[labelled_idx] = y_tr[labelled_idx]
# ── Label Propagation ─────────────────────────────────────────
lp = LabelPropagation(kernel='rbf', gamma=20, max_iter=1000)
lp.fit(X_tr_sc, y_semi)
y_pred_lp = lp.predict(X_te_sc)
acc_lp = accuracy_score(y_te, y_pred_lp)
# ── Label Spreading ───────────────────────────────────────────
ls = LabelSpreading(kernel='rbf', gamma=20, alpha=0.2, max_iter=1000)
ls.fit(X_tr_sc, y_semi)
y_pred_ls = ls.predict(X_te_sc)
acc_ls = accuracy_score(y_te, y_pred_ls)
# ── Supervised baseline (25 labels) ──────────────────────────
from sklearn.linear_model import LogisticRegression
lr = LogisticRegression().fit(X_tr_sc[labelled_idx], y_tr[labelled_idx])
acc_sup = accuracy_score(y_te, lr.predict(X_te_sc))
print("=== Label Propagation — Parkinson's Staging ===")
print(f"Supervised (25 labels) Accuracy : {acc_sup:.4f}")
print(f"Label Propagation Accuracy : {acc_lp:.4f}")
print(f"Label Spreading Accuracy : {acc_ls:.4f}")
print("\nLabel Spreading Report:")
print(classification_report(y_te, y_pred_ls, target_names=['Early','Late']))
# ── Show pseudo-label confidence ─────────────────────────────
proba = ls.predict_proba(X_te_sc)
confident = np.max(proba, axis=1) > 0.9
print(f"\nHigh-confidence (>0.9) test predictions: {confident.sum()}/{len(confident)}")
print(f" Accuracy on high-conf subset: {accuracy_score(y_te[confident], y_pred_ls[confident]):.4f}")
library(RSSL); set.seed(42)
# ── Simulate Biomarker Data ───────────────────────────────────
N <- 800
X1 <- rnorm(N); X2 <- rnorm(N); X3 <- rnorm(N)
y <- factor(as.integer((X1+X3-X2) > 0), labels=c("Early","Late"))
df <- data.frame(X1,X2,X3,y)
idx <- sample(1:N, 0.8*N)
tr <- df[idx,]; te <- df[-idx,]
# ── 25 labelled, rest unlabelled ─────────────────────────────
l_idx <- sample(1:nrow(tr), 25)
u_idx <- setdiff(1:nrow(tr), l_idx)
X_l <- as.matrix(tr[l_idx, 1:3]); y_l <- tr$y[l_idx]
X_u <- as.matrix(tr[u_idx, 1:3])
X_te <- as.matrix(te[, 1:3]); y_te <- te$y
# ── Label Propagation ─────────────────────────────────────────
lp_model <- LabelPropagation(X_l, y_l, X_u)
preds <- predict(lp_model, X_te)
acc_lp <- mean(preds == y_te)
# ── Supervised baseline ───────────────────────────────────────
sup <- glm(y~., data=tr[l_idx,], family=binomial())
p <- predict(sup, te, type="response")
acc_sup <- mean(factor(p>0.5,labels=c("Early","Late"))==y_te)
cat(sprintf("Supervised (25) Accuracy: %.4f\n", acc_sup))
cat(sprintf("Label Propagation Accuracy: %.4f\n", acc_lp))
# ── Confusion matrix ─────────────────────────────────────────
cat("\nLabel Propagation Confusion Matrix:\n")
print(table(Predicted=preds, Actual=y_te))
The same information as the assumption blocks above, side by side — this is the comparison that decides which method to reach for.
| Algorithm | Assumes | Breaks when |
|---|---|---|
| 3.3 Label Propagation | Manifold assumption: nearby points share labels | A new point arrives — the graph must be rebuilt and the method re-run |