Title: Wasserstein Soft Label Propagation on Hypergraphs: Algorithm and Generalization Error Bounds,
Abstract: Inspired by recent interests of developing machine learning and data mining
algorithms on hypergraphs, we investigate in this paper the semi-supervised
learning algorithm of propagating "soft labels" (e.g. probability
distributions, class membership scores) over hypergraphs, by means of optimal
transportation. Borrowing insights from Wasserstein propagation on graphs
[Solomon et al. 2014], we re-formulate the label propagation procedure as a
message-passing algorithm, which renders itself naturally to a generalization
applicable to hypergraphs through Wasserstein barycenters. Furthermore, in a
PAC learning framework, we provide generalization error bounds for propagating
one-dimensional distributions on graphs and hypergraphs using 2-Wasserstein
distance, by establishing the \textit{algorithmic stability} of the proposed
semi-supervised learning algorithm. These theoretical results also shed new
lights upon deeper understandings of the Wasserstein propagation on graphs.