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":
- Directed Graphs: Standard graph Laplacians do not naturally handle directed edges, often resulting in complex, non-convex optimization problems.
- Community Trapping: In networks with dense clusters, random walks tend to get "trapped" in local neighborhoods, failing to propagate information across the entire graph.
- 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.
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).
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