ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Information Science and Technology 02 May 2023

Coded computing for distributed graph-based semi-supervised learning

  • School of Information Science and Technology, University of Science of Technology of China, Hefei 230027, China

Cite this:
https://doi.org/10.52396/JUSTC-2022-0133
More Information
  • Author Bio:

    Siqi Tan received the B.E. degree in Electronic Information Engineering from the University of Science and Technology of China (USTC) in 2020. Now she is currently pursuing the M.E. degree at the Department of Electronic Engineering and Information Science, USTC. Her research interests include wireless communications and coded distributed computation

    Li Chen received the B.E. degree in Electrical and Information Engineering from the Harbin Institute of Technology in 2009, and the Ph.D. degree in Electrical Engineering from the University of Science and Technology of China (USTC) in 2014. He is currently an Associate Professor at the Department of Electronic Engineering and Information Science, USTC. His research interests include integrated computation and communication, integrated sensing, and communication

  • Corresponding author: E-mail: chenli87@ustc.edu.cn
  • Received Date: 17 September 2022
  • Accepted Date: 15 November 2022
    • Available Online: 02 May 2023
    Abstract

  • Abstract

    Semi-supervised learning (SSL) has been applied to many practical applications over the past few years. Recently, distributed graph-based semi-supervised learning (DGSSL) has been shown to have good performance. Current DGSSL algorithms usually have the problems of inefficient graph construction and the straggler effect. This paper proposes a novel coded DGSSL (CDGSSL) to solve these problems. We first provide a novel parallel and distributed solution of matrix completion for efficient graph construction. Then, we develop the CDGSSL algorithm based on coding theory. Specifically, the proposed algorithm consists of two parts separately designed based on the maximum distance separable (MDS) code. In general, the proposed coded distributed algorithm is efficient and straggler tolerant. Moreover, we provide an optimal parameter design for the proposed algorithm. The results of the experiments on the Alibaba Cloud elastic compute service (ECS) demonstrate the superiority of the proposed algorithm.

    Graphical abstract

    The proposed algorithm consists of two parts: coded matrix completion and coded label propagation.

    Abstract

    Semi-supervised learning (SSL) has been applied to many practical applications over the past few years. Recently, distributed graph-based semi-supervised learning (DGSSL) has been shown to have good performance. Current DGSSL algorithms usually have the problems of inefficient graph construction and the straggler effect. This paper proposes a novel coded DGSSL (CDGSSL) to solve these problems. We first provide a novel parallel and distributed solution of matrix completion for efficient graph construction. Then, we develop the CDGSSL algorithm based on coding theory. Specifically, the proposed algorithm consists of two parts separately designed based on the maximum distance separable (MDS) code. In general, the proposed coded distributed algorithm is efficient and straggler tolerant. Moreover, we provide an optimal parameter design for the proposed algorithm. The results of the experiments on the Alibaba Cloud elastic compute service (ECS) demonstrate the superiority of the proposed algorithm.

    • Public Summary

    • Existing distributed graph-based semi-supervised learning algorithms suffer from extensive communication and computation. The proposed scheme is more efficient with low complexity by providing a parallel and distributed solution for global Euclidean distance matrix completion.
    • The iteration time of distributed graph-based semi-supervised learning is defined by the slowest node, noted as the straggler node. A novel coded computation design for distributed graph-based semi-supervised learning is proposed to decrease the straggler effect.
    • We numerically verified the superiority of the proposed scheme on Alibaba cloud elastic compute service. In general, the simulation results have demonstrate that our proposed algorithm is efficient and straggler tolerant.

    FullText(HTML)
  • loading
    • References(31)
  • [1]
    van Engelen J E, Hoos H H. A survey on semi-supervised learning. Machine Learning, 2020, 109: 373–440. doi: 10.1007/s10994-019-05855-6
    [2]
    Ang J C, Mirzal A, Haron H, et al. Supervised, unsupervised, and semi-supervised feature selection: A review on gene selection. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2016, 13 (5): 971–989. doi: 10.1109/tcbb.2015.2478454
    [3]
    Zhu X, Goldberg A B. Introduction to Semi-Supervised Learning. Cham, Switzerland: Springer, 2009.
    [4]
    Scudder H. Probability of error of some adaptive pattern-recognition machines. IEEE Transactions on Information Theory, 1965, 11 (3): 363–371. doi: 10.1109/tit.1965.1053799
    [5]
    Blum A, Mitchell T. Combining labeled and unlabeled data with co-training. In: COLT' 98: Proceedings of the Eleventh Annual Conference on Computational Learning Theory. New York: ACM, 1998: 92–100.
    [6]
    Belkin M, Niyogi P, Sindhwani V. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 2006, 7: 2399–2434. doi: 10.5555/1248547.1248632
    [7]
    Belkin M, Niyogi P. Semi-supervised learning on Riemannian manifolds. Machine Learning, 2004, 56: 209–239. doi: 10.1023/B:MACH.0000033120.25363.1e
    [8]
    Chapelle O, Schölkopf B, Zien A, Transductive support vector machines. In: Semi-Supervised Learning. Cambridge: MIT Press. 2006, 105–117.
    [9]
    Chong Y, Ding Y, Yan Q, et al. Graph-based semi-supervised learning: A review. Neurocomputing, 2020, 408 (30): 216–230. doi: 10.1016/j.neucom.2019.12.130
    [10]
    Zhu X, Ghahramani Z, Lafferty J. Semi-supervised learning using Gaussian fields and harmonic functions. In: ICML'03: Proceedings of the Twentieth International Conference on International Conference on Machine Learning. Washington, DC: AAAI Press, 2003: 912–919.
    [11]
    Zhou D, Bousquet O, Lal T N, et al. Learning with local and global consistency. In: NIPS'03: Proceedings of the 16th International Conference on Neural Information Processing Systems. New York: ACM, 2003: 321–328.
    [12]
    Chen J, Wang C, Sun Y, et al. Semi-supervised Laplacian regularized least squares algorithm for localization in wireless sensor networks. Computer Networks, 2011, 55 (10): 2481–2491. doi: 10.1016/j.comnet.2011.04.010
    [13]
    Szummer M, Jaakkola T. Partially labeled classification with Markov random walks. In: NIPS'01: Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic. Cambridge: MIT Press, 2001: 945–952.
    [14]
    Grira N, Crucianu M, Boujemaa N. Active semi-supervised fuzzy clustering for image database categorization. In: MIR '05: Proceedings of the 7th ACM SIGMM International Workshop on Multimedia Information Retrieval. New York: ACM, 2005: 9–16.
    [15]
    Chapelle O, Zien A. Semi-supervised classification by low density separation. In: AISTATS 2005–Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics. Stuttgart, Germany: Max-Planck-Gesellschaft, 2005: 57–64.
    [16]
    Kostopoulos G, Karlos S, Kotsiantis S, et al. Semi-supervised regression: A recent review. Journal of Intelligent & Fuzzy Systems, 2018, 35 (2): 1483–1500. doi: 10.3233/JIFS-169689
    [17]
    Torii M, Wagholikar K, Liu H. Using machine learning for concept extraction on clinical documents from multiple data sources. Journal of the American Medical Informatics Association, 2011, 18: 580–587 . doi: 10.1136/amiajnl-2011-000155
    [18]
    Scardapane S, Fierimonte R, Wang D, et al. Distributed music classification using random vector functional-link nets. In: 2015 International Joint Conference on Neural Networks (IJCNN). Killarney, Ireland: IEEE, 2015: 1–8.
    [19]
    Shih T K, Distributed multimedia databases In: Shih T K, editor. Distributed Multimedia Databases: Techniques and Applications. Hershey, PA: IGI Global, 2002: 2–12.
    [20]
    Shen P, Du X, Li C. Distributed semi-supervised metric learning. IEEE Access, 2016, 4: 8558–8571. doi: 10.1109/ACCESS.2016.2632158
    [21]
    Scardapane S, Fierimonte R, Di Lorenzo P, et al. Distributed semi-supervised support vector machines. Neural Networks, 2016, 80: 43–52 . doi: 10.1016/j.neunet.2016.04.007
    [22]
    Fierimonte R, Scardapane S, Uncini A, et al. Fully decentralized semi-supervised learning via privacy-preserving matrix completion. IEEE Transactions on Neural Networks and Learning Systems, 2017, 28: 2699–2711. doi: 10.1109/TNNLS.2016.2597444
    [23]
    Gan H, Li Z, Wu W, et al. Safety-aware graph-based semi-supervised learning. Expert Systems With Applications, 2018, 107: 243–254. doi: 10.1016/j.eswa.2018.04.031
    [24]
    Lee K, Lam M, Pedarsani R, et al. Speeding up distributed machine learning using codes. IEEE Transactions on Information Theory, 2018, 64 (3): 1514–1529. doi: 10.1109/tit.2017.2736066
    [25]
    Chen L, Han K, Du Y, et al. Block-division-based wireless coded computation. IEEE Wireless Communications Letters, 2022, 11 (2): 283–287. doi: 10.1109/LWC.2021.3125983
    [26]
    Agarwal A, Duchi J C. Distributed delayed stochastic optimization. In: 2012 IEEE 51st IEEE Conference on Decision and Control (CDC). Maui, USA: IEEE, 2012: 5451–5452.
    [27]
    Alfakih A Y, Khandani A K, Wolkowicz H. Solving euclidean distance matrix completion problems via semidefinite programming. Computational Optimization and Applications, 1999, 12: 13–30. doi: 10.1023/A:1008655427845
    [28]
    Al-Homidan S, Wolkowicz H. Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming. Linear Algebra and Its Applications, 2005, 406: 109–141. doi: 10.1016/j.laa.2005.03.021
    [29]
    Liu W, Chen L, Zhang W. Decentralized federated learning: Balancing communication and computing costs. IEEE Transactions on Signal and Information Processing Over Networks, 2022, 8: 131–143. doi: 10.1109/TSIPN.2022.3151242
    [30]
    Liu W, Chen L, Chen Y, et al. Accelerating federated learning via momentum gradient descent. IEEE Transactions on Parallel and Distributed Systems, 2020, 31 (8): 1754–1766. doi: 10.1109/TPDS.2020.2975189
    [31]
    Wang Z, Du Y, Wei K, et al. Vision, application scenarios, and key technology trends for 6G mobile communications. Science China Information Sciences, 2022, 65: 151301. doi: 10.1007/s11432-021-3351-5
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML

    Figure  1.  Illustration of the distributed SSL setup with N client and 1 server. Each client owns a labeled data set ${{{\boldsymbol{S}}}_{i}}$ and an unlabeled data set ${{{\boldsymbol{U}}}_{i}}$. The server collects information from clients to run a distributed SSL task to estimate all the unknown labels and return the unknown label to clients.

    Figure  2.  Illustration of distributed computation for distributed SSL.

    Figure  3.  Single iteration of coded distributed matrix completion.

    Figure  4.  Single iteration of coded distributed label propagation.

    Figure  5.  The round-trip time of a task once between the central server and the client on ECS instance.

    Figure  6.  Matrix completion accuracy and classification accuracy of with rank ratio $\rho ={r}/{K+2}$.

    Figure  7.  Illustration of the random 100 images from the MNIST data set and their label after the CDGSSL task, as the rank $ r $ increased. The highlighted label is the incorrect label after the training process.

    Figure  8.  Comparison of average running time under different delay conditions overhead of uncoded algorithm and MDS-coded algorithm with $ k=9 $ and $ k=8 $.

    [1]
    van Engelen J E, Hoos H H. A survey on semi-supervised learning. Machine Learning, 2020, 109: 373–440. doi: 10.1007/s10994-019-05855-6
    [2]
    Ang J C, Mirzal A, Haron H, et al. Supervised, unsupervised, and semi-supervised feature selection: A review on gene selection. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2016, 13 (5): 971–989. doi: 10.1109/tcbb.2015.2478454
    [3]
    Zhu X, Goldberg A B. Introduction to Semi-Supervised Learning. Cham, Switzerland: Springer, 2009.
    [4]
    Scudder H. Probability of error of some adaptive pattern-recognition machines. IEEE Transactions on Information Theory, 1965, 11 (3): 363–371. doi: 10.1109/tit.1965.1053799
    [5]
    Blum A, Mitchell T. Combining labeled and unlabeled data with co-training. In: COLT' 98: Proceedings of the Eleventh Annual Conference on Computational Learning Theory. New York: ACM, 1998: 92–100.
    [6]
    Belkin M, Niyogi P, Sindhwani V. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 2006, 7: 2399–2434. doi: 10.5555/1248547.1248632
    [7]
    Belkin M, Niyogi P. Semi-supervised learning on Riemannian manifolds. Machine Learning, 2004, 56: 209–239. doi: 10.1023/B:MACH.0000033120.25363.1e
    [8]
    Chapelle O, Schölkopf B, Zien A, Transductive support vector machines. In: Semi-Supervised Learning. Cambridge: MIT Press. 2006, 105–117.
    [9]
    Chong Y, Ding Y, Yan Q, et al. Graph-based semi-supervised learning: A review. Neurocomputing, 2020, 408 (30): 216–230. doi: 10.1016/j.neucom.2019.12.130
    [10]
    Zhu X, Ghahramani Z, Lafferty J. Semi-supervised learning using Gaussian fields and harmonic functions. In: ICML'03: Proceedings of the Twentieth International Conference on International Conference on Machine Learning. Washington, DC: AAAI Press, 2003: 912–919.
    [11]
    Zhou D, Bousquet O, Lal T N, et al. Learning with local and global consistency. In: NIPS'03: Proceedings of the 16th International Conference on Neural Information Processing Systems. New York: ACM, 2003: 321–328.
    [12]
    Chen J, Wang C, Sun Y, et al. Semi-supervised Laplacian regularized least squares algorithm for localization in wireless sensor networks. Computer Networks, 2011, 55 (10): 2481–2491. doi: 10.1016/j.comnet.2011.04.010
    [13]
    Szummer M, Jaakkola T. Partially labeled classification with Markov random walks. In: NIPS'01: Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic. Cambridge: MIT Press, 2001: 945–952.
    [14]
    Grira N, Crucianu M, Boujemaa N. Active semi-supervised fuzzy clustering for image database categorization. In: MIR '05: Proceedings of the 7th ACM SIGMM International Workshop on Multimedia Information Retrieval. New York: ACM, 2005: 9–16.
    [15]
    Chapelle O, Zien A. Semi-supervised classification by low density separation. In: AISTATS 2005–Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics. Stuttgart, Germany: Max-Planck-Gesellschaft, 2005: 57–64.
    [16]
    Kostopoulos G, Karlos S, Kotsiantis S, et al. Semi-supervised regression: A recent review. Journal of Intelligent & Fuzzy Systems, 2018, 35 (2): 1483–1500. doi: 10.3233/JIFS-169689
    [17]
    Torii M, Wagholikar K, Liu H. Using machine learning for concept extraction on clinical documents from multiple data sources. Journal of the American Medical Informatics Association, 2011, 18: 580–587 . doi: 10.1136/amiajnl-2011-000155
    [18]
    Scardapane S, Fierimonte R, Wang D, et al. Distributed music classification using random vector functional-link nets. In: 2015 International Joint Conference on Neural Networks (IJCNN). Killarney, Ireland: IEEE, 2015: 1–8.
    [19]
    Shih T K, Distributed multimedia databases In: Shih T K, editor. Distributed Multimedia Databases: Techniques and Applications. Hershey, PA: IGI Global, 2002: 2–12.
    [20]
    Shen P, Du X, Li C. Distributed semi-supervised metric learning. IEEE Access, 2016, 4: 8558–8571. doi: 10.1109/ACCESS.2016.2632158
    [21]
    Scardapane S, Fierimonte R, Di Lorenzo P, et al. Distributed semi-supervised support vector machines. Neural Networks, 2016, 80: 43–52 . doi: 10.1016/j.neunet.2016.04.007
    [22]
    Fierimonte R, Scardapane S, Uncini A, et al. Fully decentralized semi-supervised learning via privacy-preserving matrix completion. IEEE Transactions on Neural Networks and Learning Systems, 2017, 28: 2699–2711. doi: 10.1109/TNNLS.2016.2597444
    [23]
    Gan H, Li Z, Wu W, et al. Safety-aware graph-based semi-supervised learning. Expert Systems With Applications, 2018, 107: 243–254. doi: 10.1016/j.eswa.2018.04.031
    [24]
    Lee K, Lam M, Pedarsani R, et al. Speeding up distributed machine learning using codes. IEEE Transactions on Information Theory, 2018, 64 (3): 1514–1529. doi: 10.1109/tit.2017.2736066
    [25]
    Chen L, Han K, Du Y, et al. Block-division-based wireless coded computation. IEEE Wireless Communications Letters, 2022, 11 (2): 283–287. doi: 10.1109/LWC.2021.3125983
    [26]
    Agarwal A, Duchi J C. Distributed delayed stochastic optimization. In: 2012 IEEE 51st IEEE Conference on Decision and Control (CDC). Maui, USA: IEEE, 2012: 5451–5452.
    [27]
    Alfakih A Y, Khandani A K, Wolkowicz H. Solving euclidean distance matrix completion problems via semidefinite programming. Computational Optimization and Applications, 1999, 12: 13–30. doi: 10.1023/A:1008655427845
    [28]
    Al-Homidan S, Wolkowicz H. Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming. Linear Algebra and Its Applications, 2005, 406: 109–141. doi: 10.1016/j.laa.2005.03.021
    [29]
    Liu W, Chen L, Zhang W. Decentralized federated learning: Balancing communication and computing costs. IEEE Transactions on Signal and Information Processing Over Networks, 2022, 8: 131–143. doi: 10.1109/TSIPN.2022.3151242
    [30]
    Liu W, Chen L, Chen Y, et al. Accelerating federated learning via momentum gradient descent. IEEE Transactions on Parallel and Distributed Systems, 2020, 31 (8): 1754–1766. doi: 10.1109/TPDS.2020.2975189
    [31]
    Wang Z, Du Y, Wei K, et al. Vision, application scenarios, and key technology trends for 6G mobile communications. Science China Information Sciences, 2022, 65: 151301. doi: 10.1007/s11432-021-3351-5
    Recommended articles
    TrendMD
    Volume 53 Issue 4 page: 0401
    Cover

    Article Metrics

    Article views (620) PDF downloads(1949)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return