Abstract
We propose two asynchronously distributed approaches for graph-based semi-supervised learning. The first approach is based on stochastic approximation, whereas the second approach is based on randomized Kaczmarz algorithm. In addition to the possibility of distributed implementation, both approaches can be naturally applied online to streaming data. We analyse both approaches theoretically and by experiments. It appears that there is no clear winner and we provide indications about cases of superiority for each approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Avrachenkov, K., Dobrynin, V., Nemirovsky, D., Pham, S.K. Smirnova, E.: PageRank based clustering of hypertext document collections. In: Proceedings of ACM SIGIR (2008)
Avrachenkov, K., Gonçalves, P., Mishenin, A., and Sokol, M.: Generalized optimization framework for graph-based semi-supervised learning. In: Proceedings of SDM (2012)
Avrachenkov, K., Chebotarev, P., Mishenin, A.: Semi-supervised learning with regularized Laplacian. Accepted in Optimization Methods & Software (2016)
Bengio, Y., Delalleau, O., Le Roux, N.: Label propagation and quadratic criterion. In: Semi-supervised Learning, ch. 10 (2006)
Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice Hall, Englewood Cliffs (1989)
Borkar, V.S.: Stochastic Approximation: A Dynamical Systems Viewpoint. Hindustan Publishing Agency, Cambridge University Press, New Delhi, Cambridge (2008)
Borkar, V.S., Karamchandani, N., Mirani, S.: Randomized Kaczmarz for rank aggregation from pairwise comparisons. In: IEEE ITW (2016)
Chapelle, O., Schölkopf, B., Zien, A.: Semi-supervised Learning. MIT Press, London (2006)
Chebotarev, P., Shamis, E.: The matrix-forest theorem and measuring relations in small social groups. Autom. Remote Control 58(9), 1505–1514 (1997)
Craven, M., McCallum, A., PiPasquo, D., Mitchell, T., Freitag, D.: Learning to extract symbolic knowledge from the World Wide Web (No. CMU-CS-98-122). School of computer Science, Carnegie-Mellon University, Pittsburgh, PA (1998)
Fouss, F., Francoisse, K., Yen, L., Pirotte, A., Saerens, M.: An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification. Neural Netw. 31, 53–72 (2012)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. PNAS USA 99, 7821–7826 (2002)
Gleich, D.F., Mahoney, M.W.: Using local spectral methods to robustify graph-based learning algorithms. In: Proceedings of ACM SIGKDD (2015)
Gower, R.M., Richtárik, P.: Randomized iterative methods for linear systems. SIAM J. Matrix Anal. Appl. 36(4), 1660–1690 (2015)
Ito, T., Shimbo, M., Kudo, T., Matsumoto, Y.: Application of kernels to link analysis. In: Proceedings of ACM SIGKDD (2005)
Liu, J., Wright, S.J., Sridhar, S.: An asynchronous parallel randomized Kaczmarz algorithm (2014). arXiv preprint: arXiv:1401.4780
Needell, D., Ward, R., Srebro, N.: Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In: Proceedings of NIPS (2014)
Pan, J.J., Pan, S.J., Yin, J., Ni, L.M., Yang, Q.: Tracking mobile users in wireless networks via semi-supervised colocalization. IEEE Trans. Pattern Anal. Mach. Intell. 34(3), 587–600 (2012)
Ravi, S., Diao, Q.: Large scale distributed semi-supervised learning using streaming approximation. In: Proceedings of AISTATS (2016)
Shivanna, R., Chatterjee, B.K., Sankaran, R., Bhattacharyya, C., Bach, F.: Spectral norm regularization of orthonormal representations for graph transduction. In: Advances in Neural Information Processing Systems, pp. 2215–2223 (2015)
Smola, A.J., Kondor, R.: Kernels and regularization on graphs. In: Schölkopf, B., Warmuth, M.K. (eds.) COLT-Kernel 2003. LNCS (LNAI), vol. 2777, pp. 144–158. Springer, Heidelberg (2003). doi:10.1007/978-3-540-45167-9_12
Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15(2), 262–278 (2009)
Talukdar, P.P., Crammer, K.: New regularized algorithms for transductive learning. In: Buntine, W., Grobelnik, M., Mladenić, D., Shawe-Taylor, J. (eds.) ECML PKDD 2009. LNCS (LNAI), vol. 5782, pp. 442–457. Springer, Heidelberg (2009). doi:10.1007/978-3-642-04174-7_29
Valko, M., Kveton, B., Huang, L., Ting, D.: Online semi-supervised learning on quantized graphs. In: Proceedings of UAI (2010)
Zhou, D., Bousquet, O., Lal, T.N., Weston, J., Schölkopf, B.: Learning with local and global consistency. Adv. Neural Inf. Process. Syst. 16, 321–328 (2004)
Zhou, D., Burges, C.J.: Spectral clustering and transductive learning with multiple views. In: Proceedings of ICML (2007)
Zhu, X., Ghahramani, Z., Lafferty, J.: Semi-supervised learning using Gaussian fields and harmonic functions. In: Proceedings of ICML (2003)
Zhu, X.: Semi-supervised learning: literature survey. University of Wisconsin-Madison Research report TR 1530 (2005)
Zhu, X., Goldberg, A.B.: Introduction to Semi-supervised Learning. Morgan & Claypool, San Rafael (2009)
Zouzias, A., Freris, N.M.: Randomized gossip algorithms for solving Laplacian systems. In: Proceedings of ECC (2015)
Acknowledgement
This work was supported by CEFIPRA grant no. 5100-IT1 “Monte Carlo and Learning Schemes for Network Analytics,” and Inria Nokia Bell Labs.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Avrachenkov, K., Borkar, V.S., Saboo, K. (2016). Distributed and Asynchronous Methods for Semi-supervised Learning. In: Bonato, A., Graham, F., Prałat, P. (eds) Algorithms and Models for the Web Graph. WAW 2016. Lecture Notes in Computer Science(), vol 10088. Springer, Cham. https://doi.org/10.1007/978-3-319-49787-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-49787-7_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49786-0
Online ISBN: 978-3-319-49787-7
eBook Packages: Computer ScienceComputer Science (R0)