TY - JOUR AU - Gao, Tingran AU - Asoodeh, Shahab AU - Huang, Yi AU - Evans, James PY - 2019/07/17 Y2 - 2024/03/28 TI - Wasserstein Soft Label Propagation on Hypergraphs: Algorithm and Generalization Error Bounds JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 33 IS - 01 SE - AAAI Technical Track: Machine Learning DO - 10.1609/aaai.v33i01.33013630 UR - https://ojs.aaai.org/index.php/AAAI/article/view/4244 SP - 3630-3637 AB - <p>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 <em>algorithmic stability</em> of the proposed semisupervised learning algorithm. These theoretical results also shed new lights upon deeper understandings of the Wasserstein propagation on graphs.</p> ER -