Graph Label Propagation

Graph label propagation is a semi-supervised machine learning algorithm that infers labels for unlabelled nodes in a graph based on the labels of a few known nodes and the weighted edges connecting them. This process can be interpreted as finding the harmonic function on the graph, which minimizes the total energy (or tension) of the edges.

Worked Example

Let's calculate the propagation for a specific case:

Set the left edge weight to 2 (w_left = 2).
Set the middle edge weight to 1 (w_middle = 1).
Set the right edge weight to 1 (w_right = 1).

First, calculate the resistances:

R_left = 1/2 = 0.5
R_middle = 1/1 = 1
R_right = 1/1 = 1

Sum of resistances: Σ R = 0.5 + 1 + 1 = 2.5

Now calculate the node scores:

f₁ = 0.5 / 2.5 = 1/5 = 0.2
f₂ = 1.5 / 2.5 = 3/5 = 0.6

And the total energy:

E = 1 / 2.5 = 2/5 = 0.4

Experiment

Use the module controls to explore how edge weights influence the label propagation:

Set Left edge weight, Middle edge weight and Right edge weight to 1. Read node scores 0.333333 and 0.666667, and energy 0.333333.
Set Left edge weight to 2, keeping the other two at 1. Read scores 0.200000 and 0.600000, and energy 0.400000. The left edge more strongly pulls its adjacent score toward zero.
Set all three edge weights to 4. The scores return to 0.333333 and 0.666667, while energy rises to 1.333333: uniform weight scaling changes energy, not the minimizer.
Drag the graph or use arrow keys to pan. Press Home or Reset view to return without changing the weights or scores.

Limitations

This implementation assumes a very simple, fixed 1D chain of 4 nodes. Real-world applications typically involve large, complex graphs with many unlabelled nodes and potentially unlabeled islands (components disconnected from any labeled nodes). We also do not support zero-weight cases here, which would represent disconnected components and lead to undefined states (division by zero) in this simplified formulation. The scores here are interpreted as random-walk hitting probabilities rather than measured classification accuracy.

References

The primary foundation for this harmonic approach to semi-supervised learning on graphs can be found in the seminal 2003 paper by Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Their work demonstrated how finding the harmonic function on the graph minimizes the edge energy, effectively propagating labels from known points to unknown ones.

Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions (Zhu et al., 2003)

Graph Label Propagation