Abstract

The main idea behind graph-based semi–supervised learning is to use pair–wise similarities between data instances to enhance classification accuracy (see (Zhu, 2005) for a survey of existing approaches). Many graph–based techniques use certain type of regularization that often involve a graph Laplacian operator (eg, see (Belkin et al., 2006)). Intuitively, this corresponds to a diffusion process on graphs, where the information is propagated from the labeled instances to the rest of the nodes. Usually, this information is represented as a continuos class–membership probabilities (or scores), and the propagation process corresponds to the diffusion of those scores through the graph.
We contrast this type of continuos diffusion approach by a closely related, but a different one. Specifically, instead of heat–diffusion like process, we consider a discrete, epidemic–like process, where one propagates categorical variables (such as class labels) rather than class membership probabilities. This can be done by combining the diffusion operator with a non–linear transformation that maps the class probabilities onto class labels at each iteration step. We refer to the diffusion and epidemic based approaches as Score Propagation (SP) and Label Propagation (LP), respectively.

Date

March 5, 2026

Authors

Aram Galstyan, Paul R Cohen

Journal

6th International Workshop on Mining and Learning with Graphs