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. In many graph-based methods, labels can be thought of as propagating over the graph, where the underlying propagation mechanism is based on random walks or on averaging dynamics. While theoretically elegant, these dynamics suffer from several drawbacks which can hurt predictive performance. Our goal in this work is to explore alternative mechanisms for propagating labels. In particular, we propose a method based on dynamic infection processes, where unlabeled nodes can be "infected" with the label of their already infected neighbors. Our algorithm is efficient and scalable, and an analysis of the underlying optimization objective reveals a surprising relation to other Laplacian approaches. We conclude with a thorough set of experiments across multiple benchmarks and various learning settings.

Introduction

In modern machine learning, the scarcity of labeled data remains a primary bottleneck. Semi-supervised learning (SSL) addresses this by leveraging a small set of labeled examples alongside a much larger pool of unlabeled data. The core assumption in graph-based SSL is "smoothness": data points that are close to each other in a graph should likely share the same label. Traditionally, this is achieved through Label Propagation (LabelProp), which utilizes random walks or local averaging to spread information.

However, traditional LabelProp suffers from three major "pathologies":

  1. Directed Graphs: Standard graph Laplacians do not naturally handle directed edges, often resulting in complex, non-convex optimization problems.
  2. Community Trapping: In networks with dense clusters, random walks tend to get "trapped" in local neighborhoods, failing to propagate information across the entire graph.
  3. Signal Decay: When labels are extremely scarce, the steady state of a random walk often becomes uniform and uninformative, losing the specific signal of the original labeled seeds.

Methodology: Infection Propagation (InfProp)

To overcome these limitations, we introduce InfProp, a method based on competitive infection dynamics. In this model, each labeled node is considered "infected" with its specific class. These nodes attempt to infect their neighbors over time. When an unlabeled node has neighbors with different labels, these labels compete to infect the node first.

Qualitative comparison of label propagation mechanisms. InfProp (left) achieves higher accuracy and more coherent cluster coverage compared to traditional LabelProp (center) and deterministic Shortest Paths (right).

The Shortest Path Equivalence

Simulating stochastic infections directly is computationally prohibitive. A key technical insight of this work is the proof that the probability of a node being infected by a specific label is equivalent to finding the shortest path in a random graph where edge weights represent stochastic "incubation times." By leveraging this equivalence, we developed an efficient algorithm based on a modified Dijkstra’s approach. This allows for a "Fully Polynomial-Time Randomized Approximation Scheme" (FPRAS), ensuring the method scales to massive datasets with a complexity of $O(m + n \log n)$ per iteration.

Experimental Evaluation

We evaluated InfProp across a diverse range of benchmarks, including citation graphs (CoRA, CiteSeer, PubMed), social networks (Flickr, YouTube), and product-link networks (Amazon). These datasets cover multiclass and multilabel settings, both with and without node features.

Key Insights

  • Global Sensitivity: Unlike standard methods where edge weights are fixed locally, InfProp’s "effective" weights depend on the global graph structure and seed locations, allowing it to better capture the data's geometry.
  • Robustness: By using an ensemble of paths rather than a single deterministic shortest path, InfProp remains resilient to noise and outliers that might otherwise bridge unrelated clusters.
  • Laplacian Connection: Analysis reveals that InfProp minimizes a quadratic objective function similar to traditional methods, but utilizes a "non-homogeneous" Laplacian that is automatically tuned by the infection dynamics.

Results

InfProp consistently outperformed classic baselines and modern deep learning approaches like DeepWalk and Planetoid. The performance gap was most pronounced in scenarios with extreme label scarcity (e.g., only 1% of data labeled).

Performance comparison across different learning settings. InfProp consistently outperforms baselines in multiclass (with and without features) and multilabel tasks, particularly when labeled data is scarce.

As shown in the experimental results, InfProp (represented by the orange line) maintains a significant lead in accuracy across various seed sizes. On the CoRA dataset without features, InfProp achieved an accuracy of 0.59, compared to just 0.41 for traditional LabelProp.

Conclusion

InfProp offers a scalable and theoretically grounded alternative to traditional random-walk-based label propagation. By treating labels as competing infections, the model effectively navigates complex community structures and directed edges. Future work will focus on automated hyperparameter tuning for the activation probability ($p$) and incubation time distributions to further enhance the model's adaptability to diverse network topologies.

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 examples. In many graph-based methods, labels can be thought of as propagating over the graph, where the underlying propagation mechanism is based on random walks or on averaging dynamics. While theoretically elegant, these dynamics suffer from several drawbacks which can hurt predictive performance. Our goal in this work is to explore alternative mechanisms for propagating labels. In particular, we propose a method based on dynamic infection processes, where unlabeled nodes can be "infected" with the label of their already infected neighbors. Our algorithm is efficient and scalable, and an analysis of the underlying optimization objective reveals a surprising relation to other Laplacian approaches. We conclude with a thorough set of experiments across multiple benchmarks and various learning settings.
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},
}

Loading related content...

Figure