Label Propagation

Summary

Label Propagation is a semi-supervised learning algorithm that classifies unlabeled data by progressively diffusing the information contained in the few available labeled samples. Rather than building an explicit parametric model, this algorithm exploits the local structure of the entire dataset: it builds a similarity graph between all points, then propagates the known labels through the edges of this graph iteratively, until convergence. Its sibling, Label Spreading, introduces a regularization parameter alpha that controls the trade-off between fidelity to the initial labels and the influence of propagated neighbors. These two algorithms are particularly useful when acquiring labels is expensive — an extremely common scenario in industrial practice.

Mathematical Principle

Label Propagation relies on an elegant matrix formulation that transforms the classification problem into a diffusion process on a graph. Here are the fundamental mathematical ingredients.

Similarity Matrix

We start by building a similarity matrix W between all pairs of points. The entry W_ij measures the proximity between two samples x_i and x_j. The most common definition uses a radial basis function (RBF) kernel:

W_ij = exp(-||x_i - x_j||² / (2·sigma²))

where sigma is a diffusion parameter that controls the kernel’s reach. Another popular approach uses k nearest neighbors: edges are only kept between each point and its k closest neighbors, which makes the matrix W sparse and significantly speeds up computations.

Label Matrix

We define a label matrix Y of dimension n × C, where n is the total number of samples (labeled and unlabeled) and C is the number of classes. Rows corresponding to labeled samples contain one-hot vectors (a 1 at the position of the known label, 0s elsewhere). Rows for unlabeled samples are initialized to uniform or zero values.

In classical Label Propagation, known labels are clamped (fixed) at each iteration: they never change. Only the rows corresponding to unlabeled data are updated.

Iterative Propagation

The fundamental iteration is written as follows:

F(t+1) = S · F(t)

where S = D^{-1/2} W D^{-1/2} is the symmetric normalized transition matrix and D is the diagonal degree matrix (D_ii = sum_j W_ij). Symmetric normalization guarantees that the eigenvalues of S are bounded between -1 and 1, which is crucial for numerical stability.

For Label Spreading, the iteration becomes:

F(t+1) = alpha · S · F(t) + (1 - alpha) · Y(0)

where Y(0) is the initial label matrix (which remains fixed), and alpha ∈ ]0, 1[ controls the trade-off between propagation (first term) and retention of initial information (second term). When alpha is close to 1, the algorithm primarily trusts the graph structure; when alpha is close to 0, it remains faithful to the initial labels.

Guaranteed Convergence

Convergence is mathematically guaranteed because 0 < alpha < 1. The eigenvalues of the matrix alpha · S are strictly between -1 and 1, which means the sequence F(t) converges toward a unique fixed point. In practice, convergence is generally reached in less than a hundred iterations, even for significantly sized datasets.

Once convergence is reached, the predicted class for each unlabeled sample is simply the one that maximizes the corresponding value in the final matrix F:

y_i_pred = argmax_c F_ic

Intuition

Imagine a large room full of people. A few of them already know the answer to a question — say, they know which group each individual belongs to. The others know nothing at all.

Now imagine that each person looks at their nearest neighbors (those most similar to them) and communicates what they know. People who already possess the original information (known labels) constantly repeat their answer: at each turn, they reaffirm their position. People without initial information, on the other hand, progressively accumulate what they hear from their neighbors, weighted by similarity.

Over iterations, a kind of structured rumor spreads through the crowd. Each person ends up hearing more messages of a certain type than others, and this dominant message becomes their predicted label. People who are very close (very similar) to labeled individuals receive clear information quickly; those who are farther away receive a more diffused signal, but it still converges toward the correct answer through iterative repetition.

This analogy perfectly captures the essence of the algorithm: local similarity replaces global modeling. Rather than learning a complex decision boundary as a neural network or SVM would, Label Propagation lets the intrinsic structure of the data “speak for itself.” The similarity graph encodes the entire geometry of the problem, and propagation does the rest.

Python Implementation

Preparing Synthetic Data

Let’s start by generating synthetic data with a small percentage of labeled samples, then compare the two scikit-learn algorithms.

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.semi_supervised import LabelPropagation, LabelSpreading
from sklearn.metrics import accuracy_score, classification_report

# Generate synthetic data in the shape of concentric circles
X, y_true = datasets.make_circles(n_samples=1000, factor=0.5, noise=0.1, random_state=42)

# Create labels: only 10% are labeled
rng = np.random.RandomState(42)
labeled_mask = rng.random(len(y_true)) < 0.10
y_labeled = -1 * np.ones(len(y_true), dtype=int)  # -1 = unlabeled
y_labeled[labeled_mask] = y_true[labeled_mask]

print(f"Total samples: {len(y_true)}")
print(f"Labeled samples: {labeled_mask.sum()}")
print(f"Unlabeled samples: {(~labeled_mask).sum()}")

Label Propagation: RBF Kernel and k-Nearest Neighbors

scikit-learn offers two kernels for Label Propagation: the RBF kernel (kernel="rbf") and the k-NN kernel (kernel="knn"). Let’s look at both approaches.

# --- Label Propagation with RBF kernel ---
lp_rbf = LabelPropagation(kernel="rbf", gamma=20, max_iter=100)
lp_rbf.fit(X, y_labeled)
y_pred_rbf = lp_rbf.predict(X)

# --- Label Propagation with k-NN kernel ---
lp_knn = LabelPropagation(kernel="knn", n_neighbors=7, max_iter=100)
lp_knn.fit(X, y_labeled)
y_pred_knn = lp_knn.predict(X)

# --- Label Spreading with RBF kernel ---
ls_rbf = LabelSpreading(kernel="rbf", gamma=20, alpha=0.2, max_iter=100)
ls_rbf.fit(X, y_labeled)
y_pred_ls = ls_rbf.predict(X)

# --- Label Spreading with k-NN kernel ---
ls_knn = LabelSpreading(kernel="knn", n_neighbors=7, alpha=0.2, max_iter=100)
ls_knn.fit(X, y_labeled)
y_pred_ls_knn = ls_knn.predict(X)

# Evaluation
print("\n=== Results ===")
for name, y_pred in [
    ("LP RBF", y_pred_rbf),
    ("LP k-NN", y_pred_knn),
    ("LS RBF", y_pred_ls),
    ("LS k-NN", y_pred_ls_knn),
]:
    acc = accuracy_score(y_true, y_pred)
    print(f"{name:15s} — Accuracy: {acc:.4f}")

Visualizing Decision Boundaries

Visualizing decision boundaries helps understand how each variant partitions the feature space.

def plot_decision_boundaries(X, y_true, y_labeled, title):
    # Grid for the boundary
    x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
    y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
    xx, yy = np.meshgrid(
        np.linspace(x_min, x_max, 300),
        np.linspace(y_min, y_max, 300),
    )
    grid_points = np.c_[xx.ravel(), yy.ravel()]

    kernel_type = "rbf" if "RBF" in title else "knn"
    if "Spreading" in title:
        model = LabelSpreading(
            kernel=kernel_type,
            gamma=20 if kernel_type == "rbf" else None,
            n_neighbors=7 if kernel_type == "knn" else None,
            alpha=0.2,
            max_iter=100,
        )
    else:
        model = LabelPropagation(
            kernel=kernel_type,
            gamma=20 if kernel_type == "rbf" else None,
            n_neighbors=7 if kernel_type == "knn" else None,
            max_iter=100,
        )
    model.fit(X, y_labeled)
    Z = model.predict(grid_points).reshape(xx.shape)

    fig, ax = plt.subplots(1, 1, figsize=(10, 8))
    ax.contourf(xx, yy, Z, alpha=0.3, cmap="RdBu")

    unlabeled_mask = y_labeled == -1
    ax.scatter(X[unlabeled_mask, 0], X[unlabeled_mask, 1],
        c=y_true[unlabeled_mask], cmap="RdBu", s=20, alpha=0.4, label="Unlabeled")
    ax.scatter(X[~unlabeled_mask, 0], X[~unlabeled_mask, 1],
        c=y_true[~unlabeled_mask], cmap="RdBu", s=80,
        edgecolors="black", linewidths=1.5, label="Labeled")

    ax.set_title(title, fontsize=14, fontweight="bold")
    ax.set_xlabel("x₁")
    ax.set_ylabel("x₂")
    ax.legend(loc="upper right")
    plt.tight_layout()
    plt.savefig(f"./boundary_{title.lower().replace(' ', '_').replace('-', '_')}.png", dpi=150)
    plt.show()


plot_decision_boundaries(X, y_true, y_labeled, "LP RBF")
plot_decision_boundaries(X, y_true, y_labeled, "LP k-NN")
plot_decision_boundaries(X, y_true, y_labeled, "LS RBF")
plot_decision_boundaries(X, y_true, y_labeled, "LS k-NN")

Comparison and Analysis of Results

A crucial aspect of Label Propagation is the ability to access class probability distributions via the predict_proba() method. This allows not only knowing the predicted class, but also estimating the confidence of the prediction.

# Probabilities for unlabeled examples
probas = lp_rbf.predict_proba(X[~labeled_mask])
confidence = probas.max(axis=1)

print(f"Average confidence: {confidence.mean():.3f}")
print(f"Minimum confidence: {confidence.min():.3f}")
print(f"Standard deviation: {confidence.std():.3f}")

# Identify "uncertain" predictions
confidence_threshold = 0.6
uncertain = confidence < confidence_threshold
print(f"\nUncertain predictions (confidence < {confidence_threshold}): {uncertain.sum()}")

Analyzing confidence levels reveals valuable information about the geometry of the dataset: points near cluster boundaries naturally have lower confidence, while those at the heart of clusters benefit from very confident assignment.

Hyperparameters

The choice of hyperparameters profoundly influences the behavior of Label Propagation. Let’s examine each of them.

kernel: Kernel Choice

The kernel parameter determines how the similarity matrix is constructed. Two options are available in scikit-learn:

• "rbf" (radial basis function kernel): computes similarity between all pairs of points. This yields a complete, dense graph. The RBF kernel is smooth and produces gradual decision boundaries, but it can be very memory-intensive for large datasets: the matrix W has O(n²) complexity.
• "knn" (k nearest neighbors): only connects each point to its n_neighbors closest neighbors. The matrix W is sparse, reducing complexity to O(n·k·log(n)) and enabling processing of much larger datasets. Decision boundaries are more angular but capture local structure well.

gamma: RBF Kernel Width

The gamma parameter corresponds to 1 / (2·sigma²) in the RBF kernel formula. A high gamma produces narrow kernels: only very close points contribute significantly. A low gamma produces wider kernels: more distant points also influence propagation.

Tuning gamma is crucial. A bad choice can either fragment the graph into isolated components (gamma too high) or drown the signal in homogeneous noise (gamma too low).

alpha: Propagation / Retention Trade-off (Label Spreading only)

The alpha parameter only exists for Label Spreading. It controls the balance between two opposing forces: label propagation through the graph on one hand, and retention of the initial labels on the other.

• Alpha close to 1 (e.g., 0.8): strong propagation, weak recall. The algorithm largely trusts the graph structure. Risk of error propagation if the initial labels are noisy.
• Alpha close to 0.5 (e.g., 0.2-0.5): moderate trade-off between propagation and fidelity to known labels.
• Alpha close to 0 (e.g., 0.05): weak propagation, strong recall. The algorithm remains very faithful to the initial labels but does not explore the graph structure much.

n_neighbors: Number of Neighbors (k-NN Kernel)

When kernel="knn", the n_neighbors parameter determines the number of neighbors connected to each point. A small k captures fine local structure but risks fragmenting the graph. A large k ensures better connectivity but can introduce edges between distinct clusters. As an empirical rule, values between 5 and 15 work well in practice.

max_iter: Maximum Iterations

The max_iter parameter sets the upper limit on the number of iterations. In practice, convergence is generally reached well before this limit (often in 10 to 50 iterations). The algorithm stops when the norm of the difference between two successive iterations falls below an internal tolerance threshold (by default, tol=1e-3 in scikit-learn).

Advantages and Limits

Advantages

Label Propagation has several major strengths that explain its continued use in many application domains.

• Zero model parameters to learn: unlike classical supervised methods, there is no training phase with gradient descent. The algorithm is purely transductive: it directly produces predictions on the given points.
• Natural exploitation of data geometry: by building a similarity graph, the algorithm automatically captures non-linear structures and low-dimensional manifolds that would be difficult to model with parametric approaches.
• Conceptual simplicity: the principle of iterative diffusion is easy to understand and explain, making it a valuable educational tool and a good entry point into learning on graphs.
• Convexity and guaranteed convergence: Label Spreading optimizes a convex objective function, which guarantees the absence of local minima and convergence toward the unique optimal solution.
• Efficiency with few labels: the algorithm takes advantage of the entire dataset (labeled and unlabeled) and can produce excellent results with only 1 to 5% labeled data.

Limits

Despite its qualities, Label Propagation has important disadvantages that should be known.

• Memory complexity: with an RBF kernel, the similarity matrix W occupies O(n²) in memory. For datasets of several tens of thousands of samples, this can quickly become problematic. Even the k-NN kernel, although more efficient, requires storing a sparse matrix of size O(n·k).
• Sensitivity to hyperparameters: the choice of gamma (or n_neighbors) and alpha has a strong impact on results. There is no universal rule for determining them, and cross-validation on the labeled subset remains necessary.
• Transductive nature: the algorithm does not produce a reusable model. To classify a new point, the algorithm must be re-run including it in the graph, which is costly. This is a major difference from inductive methods such as Random Forests or neural networks.
• Sensitivity to noise and incorrect labels: if some initial labels are incorrect, propagation can amplify these errors, especially with high alpha values. Label Spreading with a moderate alpha mitigates this risk, but does not eliminate it entirely.
• Difficulty with non-separable clusters: when classes are strongly mixed in the feature space, local similarity is no longer sufficient to distinguish boundaries. In such cases, classical supervised methods can surpass Label Propagation.

Use Cases

1. Document Classification with Partial Annotation

In text mining, manually annotating thousands of documents is time-consuming and expensive. Label Propagation makes it possible to leverage a small annotated corpus (for example 200 manually labeled documents) and thousands of unlabeled documents. By building a similarity graph based on TF-IDF embeddings or vector representations from language models, the algorithm spreads labels through the semantic graph. This approach is particularly effective for topic categorization where documents on the same topic naturally form dense clusters in feature space.

2. Medical Image Annotation

Annotating medical images (radiographs, MRIs, scans) requires the expertise of qualified radiologists, making each label extremely valuable. A hospital may have a few hundred annotated images and several thousand raw images stored in its archives. By extracting visual features (via a pre-trained neural network for example) and building a similarity graph between images, Label Propagation can automatically pre-label unlabeled images. The radiologist can then review and correct only the most uncertain predictions, considerably reducing the workload.

3. Community Detection in Social Networks

Although community detection algorithms (such as Louvain or Infomap) are more commonly used, Label Propagation offers an interesting alternative approach for identifying groups in social graphs. Here, the “known labels” correspond to a few users whose community membership is known (for example, through public profiles or explicit declarations). Propagation spreads this information through the network, revealing the underlying community structure. This method is particularly useful in partially observed networks or when certain communities are well documented while others remain unknown.

4. Protein Function Prediction

In bioinformatics, Label Propagation is historically one of the first semi-supervised methods used to predict the function of uncharacterized proteins. A graph is built where nodes are proteins and edges represent sequence similarity or interaction. A few proteins have known functions (labeled), while the vast majority remain unannotated. Propagation spreads functional annotations through the interaction network, making it possible to formulate hypotheses about the function of unknown proteins. This approach is particularly relevant because statistically, proteins that physically interact are more likely to participate in common biological pathways.

See Also

• Python: Learning to Use pandas
• Creating Intersecting Ellipses in Python: Complete Guide for Visualization and Manipulation