Label Propagation
Label Propagation (Graph-Based Semi-Supervised Learning) · Also known as: LP, label spreading, graph-based semi-supervised learning, harmonic label propagation
Label Propagation is a graph-based semi-supervised learning algorithm introduced by Zhu and Ghahramani in 2002 that spreads class labels from a small set of labeled nodes to a large set of unlabeled nodes by iteratively diffusing label information along the edges of a similarity graph, exploiting the manifold structure of the data.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
+17 more
When to use it
Label Propagation is appropriate when labeled examples are scarce relative to the total dataset size, the data has an underlying cluster or manifold structure that a similarity graph can capture, and there is reason to believe the smoothness assumption holds — that nearby points (in feature space) tend to share the same label. Typical scenarios include text categorization with few annotated documents, image classification with sparse human labels, and network node classification. The method requires that the graph be connected (or at least that every unlabeled node be reachable from a labeled node). It is not suitable when the feature space does not reflect semantic similarity, when the decision boundary cuts through dense regions, or when all data is already labeled.
Strengths & limitations
- Exploits unlabeled data effectively, yielding strong accuracy with very few labeled examples.
- Closed-form convergence guarantee: the iterative update always reaches a unique fixed point.
- Naturally handles multi-class problems without modification.
- Intuitive geometric interpretation grounded in graph diffusion and harmonic analysis.
- No model parameters to optimize beyond the graph construction choices (kernel bandwidth, neighborhood size).
- Scalability: storing and operating on an n x n weight matrix is prohibitive for large datasets without sparse approximations.
- Graph construction is sensitive to the choice of kernel bandwidth sigma and neighborhood size k; poor choices degrade accuracy substantially.
- Assumes the smoothness (cluster) assumption: violating it — when decision boundaries pass through dense regions — leads to systematic misclassification.
- Transductive by default: predictions for new, unseen test points require re-running the algorithm or an inductive extension.
- Label noise on the few labeled nodes propagates and can corrupt a large portion of the graph.
Frequently asked
What is the difference between Label Propagation and Label Spreading?
Label Spreading, proposed by Zhou et al. (2004), introduces a regularization parameter alpha that controls how much each node retains its initial label versus adopting its neighbors' labels. In classic Label Propagation the labeled nodes are clamped rigidly, making them fully absorbing. Label Spreading allows labeled nodes to be partially overridden, which makes it more robust to label noise at the cost of one additional hyperparameter.
Does Label Propagation scale to large datasets?
The naive closed-form solution requires inverting an (n_U x n_U) matrix, which is infeasible for large n. In practice, a sparse k-nearest-neighbor or epsilon-radius graph reduces memory to O(nk), and the iterative update then scales roughly linearly in the number of edges per iteration. For very large graphs, approximate nearest-neighbor methods and mini-batch variants are used.
How many labeled examples are needed?
Label Propagation is specifically designed for the extreme low-label regime. Even a single labeled node per class can produce meaningful predictions if the graph structure aligns with the class boundaries, though having at least a few labeled examples per class is strongly recommended for reliability. Performance degrades as label noise increases or as the graph becomes less informative about class membership.
Can Label Propagation predict on new, unseen data points?
In its standard transductive form, no — the algorithm operates on a fixed graph and has no mechanism for predicting outside that graph. For inductive use, one common approach is to connect new points to their k-nearest neighbors in the existing graph and run a partial propagation step, or to use the converged label matrix to train a standard supervised classifier as a second stage.
Sources
- Zhu, X., & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University. link ↗
- Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the 20th International Conference on Machine Learning (ICML-2003), pp. 912–919. link ↗
- Chapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press. ISBN: 978-0-262-03358-9
How to cite this page
ScholarGate. (2026, June 3). Label Propagation (Graph-Based Semi-Supervised Learning). ScholarGate. https://scholargate.app/en/machine-learning/label-propagation
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Graph Neural Network (Network Analysis)Network analysis↔ compare
- Random ForestMachine learning↔ compare
- Spectral ClusteringMachine learning↔ compare