Label propagation is a semi-supervised machine learning algorithm highly suitable for classification tasks where a small amount of labeled data is available alongside a much larger set of unlabeled data. By leveraging the graph-based representation of the data, label propagation facilitates the spread of labels from the labeled instances to the unlabeled ones. However, like many iterative algorithms, label propagation may encounter numerical pitfalls, such as division by zero. This document delves into the mechanics of label propagation and outlines strategies to mitigate these issues.

Understanding Label Propagation

Core Concept

Label propagation constructs a graph where nodes represent data instances and edges represent similarities between nodes. Initially, only a few nodes have labels. The algorithm propagates these labels through the graph in the following manner:

1. Graph Construction: A Gaussian kernel or any weight function is used to construct a similarity graph.
2. Label Initialization: Known labels are assigned to their corresponding nodes, while unknown labels might start as a zero vector.
3. Propagation Process: Labels are iteratively updated based on their neighbors until convergence or for a fixed number of iterations.
4. Inference: After the iterations, each node is assigned the label with the highest score.

Mathematically, this is often expressed in matrix form: $$Y^{(t+1)} = \alpha WY^{(t)} + (1-\alpha)Y^{(0)}$$

Where: • $Y$ represents the label scores. • $W$ is the weight matrix derived from similarities. • $\alpha$ is a parameter controlling the propagation extent versus retention of initial labels. • $Y^{(0)}$ contains the initial label information.

Numerical Challenges

Division by Zero

The division by zero can notably occur during the normalization of similarities when calculating the weight matrix $W$. If two instances are entirely dissimilar, the sum of similarities might be zero, leading to division by zero during weight calculations.

Example:

Consider two points $x_i$ and $x_j$ such that their similarity is given by:

$$W(x\_i, x\_j) = \exp\left(-\frac{|x\_i-x\_j|^2}{2\sigma^2}\right)$$

If all similarities concerning a particular node are zero, during normalization, you encounter:

$$w\_{ij}' = \frac{W(x\_i, x\_j)}{\sum\_k W(x\_i, x\_k)}$$

If $\sum_k W(x_i, x_k) = 0$, division by zero occurs.

Strategies to Avoid Division by Zero

1. Additive Smoothing: Introduce a small constant $\epsilon$ to the denominator. • Implementation: $$w\_{ij}' = \frac{W(x\_i, x\_j)}{\sum\_k W(x\_i, x\_k) + \epsilon}$$ • Advantage: Ensures stability by making the denominator non-zero.
2. Thresholding: Limit the influence of nodes with negligible similarities. • Implementation: Ignore connections with similarities below a certain threshold before normalization.
3. Graph Sparsification: Ensure a minimum number of edges per node by sparsing the graph. • Implementation: • Use $k$-nearest neighbors instead of full connections. • Advantage: Guarantees at least $k$ influential nodes, reducing the chances of zero connections.
4. Regularization: Incorporate regularization terms to stabilize computations. • Implementation: Modify the weight update equation to include regularization: $$w\_{ij}' = \frac{W(x\_i, x\_j) + \lambda}{\sum\_k (W(x\_i, x\_k) + \lambda)}$$ • Advantage: Regularizes small similarities, making computations robust.

Key Points Summary

Conclusion

Label propagation is a powerful technique for semi-supervised learning, utilizing a small labeled dataset effectively within a large set of unlabeled instances. Addressing numerical stability, particularly division by zero, is critical for the robustness and accuracy of the algorithm. By employing strategies like additive smoothing, thresholding, and regularization, one can significantly enhance the model's performance and ensure efficient label propagation across a graph. Understanding these intricacies assists practitioners in deploying the label propagation algorithm effectively, even in challenging scenarios.