# Wasserstein Soft Label Propagation on Hypergraphs: Algorithm and Generalization Error Bounds

arXiv: https://arxiv.org/abs/1809.01833 · HTML: https://mlsanity.com/paper/1809.01833/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Sep 2018.

## Built on by (most cited first, 1 of 1)

- [Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework](https://mlsanity.com/paper/2210.12048/) (2022)

## Abstract (arXiv)

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 textitalgorithmic stability of the proposed semi-supervised learning algorithm. These theoretical results also shed new lights upon deeper understandings of the Wasserstein propagation on graphs.