Semi-Supervised Learning with Competitive Infection Models

Nir Rosenfeld, Amir Globerson

Abstract

The goal in semi-supervised learning is to effectively combine labeled and unlabeled data. One way to do this is by encouraging smoothness across edges in a graph whose nodes correspond to input examples. This paper introduces InfProp, a method that treats label propagation as a competitive infection process. By modeling how labels "infect" their neighbors over time, the authors create a scalable algorithm that outperforms traditional methods on directed graphs and complex community structures.

Introduction

In semi-supervised learning (SSL), the primary challenge is leveraging a vast amount of unlabeled data alongside a small set of labeled examples. Traditional graph-based SSL methods typically construct a similarity graph and "smooth" labels across it using random walks or local averaging, such as the standard Label Propagation algorithm. However, these methods face significant hurdles: they are often mathematically unstable on directed graphs, tend to get trapped in local neighborhoods within large networks, and lack the flexibility to incorporate prior knowledge or facilitate active learning effectively.

Methodology: Infection Propagation (InfProp)

The authors propose Infection Propagation (InfProp), which conceptualizes each labeled node as a source of a specific "infection" (its label). These infections compete to spread to unlabeled neighbors. An unlabeled node eventually adopts the label of the first infector that reaches it.

Technically, InfProp is equivalent to calculating shortest paths on a randomized version of the graph. This equivalence allows for high scalability; by adapting Dijkstra’s algorithm to handle all seed nodes simultaneously, the method achieves a complexity of $O(m + n \log n)$. Unlike standard LabelProp, which uses fixed local weights, InfProp utilizes "global" weights that adapt based on the entire graph structure and the specific set of labeled seeds.

Visual comparison of InfProp, LabelProp, and ShortPaths on a synthetic 3-cluster network. InfProp (0.91 accuracy) significantly outperforms LabelProp (0.40 accuracy) by effectively navigating community structures.

Key Insights

A core advantage of InfProp is its ability to handle "weakly inter-connected components"—communities joined by only a few edges. While random walks often fail to cross these bottlenecks, the infection process is more adept at finding these paths and correctly labeling distant components. Furthermore, because the process is stochastic, it naturally provides a measure of confidence. Nodes with a high probability of remaining uninfected indicate low confidence, serving as a robust signal for Active Learning. Prior knowledge can also be integrated as "incubation periods," where high-confidence priors result in shorter incubation times, allowing those labels to "win" the race more easily.

Experimental Results

The authors evaluated InfProp across a diverse set of benchmarks, including multiclass and multilabel datasets such as CoRA, DBLP, Flickr, and Amazon.

Performance comparison of InfProp against baselines across multiclass, multilabel, and active learning tasks. InfProp consistently shows superior accuracy, especially at low labeling rates.

InfProp consistently outperformed state-of-the-art baselines like LabelProp, DeepWalk, and Planetoid. The performance gap was most pronounced when labeled data was extremely scarce (e.g., 1% labeling). For instance, on the multilabel CoRA dataset, InfProp achieved an accuracy of 0.91, compared to 0.86 for LabelProp. In active learning scenarios, a greedy influence maximization strategy using InfProp significantly outperformed standard heuristics like high-degree node selection. Efficiency was also maintained; the "InfProp$_{0.5}$" variant (using a 50% edge activation probability) achieved roughly 99% of the full model's performance with significantly lower computational cost.

Conclusion

InfProp introduces a powerful, scalable framework for graph-based SSL by replacing random walks with competitive infection dynamics. It effectively addresses the limitations of traditional methods on directed and modular graphs. While highly effective, future work could explore learning infection parameters directly from data and further analyzing the theoretical properties of its non-linear stochastic processes.

Summary updated

Abstract

The goal in semi-supervised learning is to effectively combine labeled and unlabeled data. One way to do this is by encouraging smoothness across edges in a graph whose nodes correspond to input ex...
BibTeX
@inproceedings{rosenfeld2018semi,
  author = {Nir Rosenfeld and Amir Globerson},
  title = {{Semi-Supervised Learning with Competitive Infection Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
  url = {https://openreview.net/forum?id=sIy2vTBANxx},
}
Figure