Efficient Label Propagation

Yasuhiro Fujiwara, Go Irie
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):784-792, 2014.

Abstract

Label propagation is a popular graph-based semi-supervised learning framework. So as to obtain the optimal labeling scores, the label propagation algorithm requires an inverse matrix which incurs the high computational cost of O(n^3+cn^2), where n and c are the numbers of data points and labels, respectively. This paper proposes an efficient label propagation algorithm that guarantees exactly the same labeling results as those yielded by optimal labeling scores. The key to our approach is to iteratively compute lower and upper bounds of labeling scores to prune unnecessary score computations. This idea significantly reduces the computational cost to O(cnt) where t is the average number of iterations for each label and t << n in practice. Experiments demonstrate the significant superiority of our algorithm over existing label propagation methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-fujiwara14, title = {Efficient Label Propagation}, author = {Fujiwara, Yasuhiro and Irie, Go}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {784--792}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/fujiwara14.pdf}, url = {https://proceedings.mlr.press/v32/fujiwara14.html}, abstract = {Label propagation is a popular graph-based semi-supervised learning framework. So as to obtain the optimal labeling scores, the label propagation algorithm requires an inverse matrix which incurs the high computational cost of O(n^3+cn^2), where n and c are the numbers of data points and labels, respectively. This paper proposes an efficient label propagation algorithm that guarantees exactly the same labeling results as those yielded by optimal labeling scores. The key to our approach is to iteratively compute lower and upper bounds of labeling scores to prune unnecessary score computations. This idea significantly reduces the computational cost to O(cnt) where t is the average number of iterations for each label and t << n in practice. Experiments demonstrate the significant superiority of our algorithm over existing label propagation methods.} }
Endnote
%0 Conference Paper %T Efficient Label Propagation %A Yasuhiro Fujiwara %A Go Irie %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-fujiwara14 %I PMLR %P 784--792 %U https://proceedings.mlr.press/v32/fujiwara14.html %V 32 %N 2 %X Label propagation is a popular graph-based semi-supervised learning framework. So as to obtain the optimal labeling scores, the label propagation algorithm requires an inverse matrix which incurs the high computational cost of O(n^3+cn^2), where n and c are the numbers of data points and labels, respectively. This paper proposes an efficient label propagation algorithm that guarantees exactly the same labeling results as those yielded by optimal labeling scores. The key to our approach is to iteratively compute lower and upper bounds of labeling scores to prune unnecessary score computations. This idea significantly reduces the computational cost to O(cnt) where t is the average number of iterations for each label and t << n in practice. Experiments demonstrate the significant superiority of our algorithm over existing label propagation methods.
RIS
TY - CPAPER TI - Efficient Label Propagation AU - Yasuhiro Fujiwara AU - Go Irie BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-fujiwara14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 784 EP - 792 L1 - http://proceedings.mlr.press/v32/fujiwara14.pdf UR - https://proceedings.mlr.press/v32/fujiwara14.html AB - Label propagation is a popular graph-based semi-supervised learning framework. So as to obtain the optimal labeling scores, the label propagation algorithm requires an inverse matrix which incurs the high computational cost of O(n^3+cn^2), where n and c are the numbers of data points and labels, respectively. This paper proposes an efficient label propagation algorithm that guarantees exactly the same labeling results as those yielded by optimal labeling scores. The key to our approach is to iteratively compute lower and upper bounds of labeling scores to prune unnecessary score computations. This idea significantly reduces the computational cost to O(cnt) where t is the average number of iterations for each label and t << n in practice. Experiments demonstrate the significant superiority of our algorithm over existing label propagation methods. ER -
APA
Fujiwara, Y. & Irie, G.. (2014). Efficient Label Propagation. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):784-792 Available from https://proceedings.mlr.press/v32/fujiwara14.html.

Related Material