Label Propagation (LPA) is a semi-supervised graph algorithm that classifies unlabeled nodes by iteratively spreading known labels through the network structure — each node adopts the most frequent (or probability-weighted) label among its neighbors — exploiting the homophily assumption (connected nodes tend to share the same class) to propagate a small number of seed labels to the entire graph with near-linear time complexity $O(E)$ per iteration.
What Is Label Propagation?
- Definition: Given a graph where a small fraction of nodes have known labels and the rest are unlabeled, Label Propagation iteratively updates each unlabeled node's label to match the majority label in its neighborhood. In the probabilistic formulation, each node maintains a label distribution $Y_i in mathbb{R}^C$ (probability over $C$ classes), and the update rule is: $Y_i^{(t+1)} = frac{1}{d_i} sum_{j in mathcal{N}(i)} A_{ij} Y_j^{(t)}$, with labeled nodes' distributions clamped to their ground-truth labels after each iteration.
- Convergence: The algorithm converges when no node changes its label (hard version) or when label distributions stabilize (soft version). The soft version converges to the closed-form solution: $Y_U = (I - P_{UU})^{-1} P_{UL} Y_L$, where $P$ is the transition matrix partitioned into unlabeled (U) and labeled (L) blocks — this is equivalent to computing the absorbing random walk probabilities from each unlabeled node to each labeled node.
- Community Detection Variant: For unsupervised community detection, every node starts with a unique label, and labels propagate until communities emerge as groups of nodes sharing the same label. This requires no labeled data at all, producing communities purely from network structure.
Why Label Propagation Matters
- Extreme Scalability: LPA runs in $O(E)$ per iteration with typically 5–20 iterations to convergence — no matrix inversions, no eigendecompositions, no gradient computation. This makes it applicable to billion-edge graphs (social networks, web graphs) where GNN training is prohibitively expensive. The algorithm is trivially parallelizable since each node's update depends only on its neighbors.
- GNN Connection: Label Propagation is the "zero-parameter" special case of a Graph Neural Network — the propagation rule $Y^{(t+1)} = ilde{A}Y^{(t)}$ is identical to a GCN layer without learnable weights or nonlinearity. Understanding LPA provides intuition for why GNNs work (label information diffuses through the graph) and why they fail (over-smoothing = too many propagation steps causing all labels to converge).
- Baseline for Semi-Supervised Learning: LPA serves as the essential baseline for any graph semi-supervised learning task. If a GNN does not significantly outperform LPA, it suggests that the task is dominated by graph structure (homophily) rather than node features, and the GNN's learned representations are not adding value beyond simple label diffusion.
- Practical Deployment: Many production systems use LPA or its variants for fraud detection (propagating "fraudulent" labels from known fraud cases to suspicious accounts), content moderation (propagating "harmful" labels through user interaction networks), and recommendation (propagating interest labels through user-item graphs).
Label Propagation Variants
| Variant | Modification | Key Property |
|---------|-------------|-------------|
| Hard LPA | Majority vote, discrete labels | Fastest, but order-dependent |
| Soft LPA | Probability distributions, clamped seeds | Converges to closed-form solution |
| Label Spreading | Normalized Laplacian propagation | Handles degree heterogeneity |
| Causal LPA | Confidence-weighted propagation | Reduces error cascading |
| Community LPA | Unique initial labels, no supervision | Unsupervised community detection |
Label Propagation is peer pressure on a graph — spreading known labels through network connections to classify the unknown, providing the simplest and fastest semi-supervised learning algorithm that serves as both a practical tool for billion-scale graphs and the theoretical foundation for understanding GNN message passing.