Re-revisiting Learning on Hypergraphs: Confidence Interval and Subgradient Method
Chenzi Zhang, Shuguang Hu, Zhihao Gavin Tang, T-H. Hubert Chan
Abstract
We revisit semi-supervised learning on hypergraphs. Same as previous approaches, our method uses a convex program whose objective function is not everywhere differentiable. We exploit the non-uniqueness of the optimal solutions, and consider confidence intervals which give the exact ranges that unlabeled vertices take in any optimal solution. Moreover, we give a much simpler approach for solving the convex program based on the subgradient method. Our experiments on real-world datasets confirm that our confidence interval approach on hypergraphs outperforms existing methods, and our sub-gradient method gives faster running times when the number of vertices is much larger than the number of edges.
BibTeX
@InProceedings{pmlr-v70-zhang17d,
title = {Re-revisiting Learning on Hypergraphs: Confidence Interval and Subgradient Method},
author = {Chenzi Zhang and Shuguang Hu and Zhihao Gavin Tang and T-H. Hubert Chan},
booktitle = {Proceedings of the 34th International Conference on Machine Learning},
pages = {4026--4034},
year = {2017},
editor = {Precup, Doina and Teh, Yee Whye},
volume = {70},
series = {Proceedings of Machine Learning Research},
month = {06--11 Aug},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v70/zhang17d/zhang17d.pdf},
url = {https://proceedings.mlr.press/v70/zhang17d.html},
abstract = {We revisit semi-supervised learning on hypergraphs. Same as previous approaches, our method uses a convex program whose objective function is not everywhere differentiable. We exploit the non-uniqueness of the optimal solutions, and consider confidence intervals which give the exact ranges that unlabeled vertices take in any optimal solution. Moreover, we give a much simpler approach for solving the convex program based on the subgradient method. Our experiments on real-world datasets confirm that our confidence interval approach on hypergraphs outperforms existing methods, and our sub-gradient method gives faster running times when the number of vertices is much larger than the number of edges.}
}