{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:29:30Z","timestamp":1760146170448,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2024,10,4]],"date-time":"2024-10-04T00:00:00Z","timestamp":1728000000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100010226","name":"Scientific Research Platform Project of the Education Department of Guangdong Province","doi-asserted-by":"publisher","award":["2021KCXTD038","2022KSYS003","2022ZDJS065","PX-161241546"],"award-info":[{"award-number":["2021KCXTD038","2022KSYS003","2022ZDJS065","PX-161241546"]}],"id":[{"id":"10.13039\/501100010226","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Discipline Construction and Promotion Project of Guangdong Province","award":["2021KCXTD038","2022KSYS003","2022ZDJS065","PX-161241546"],"award-info":[{"award-number":["2021KCXTD038","2022KSYS003","2022ZDJS065","PX-161241546"]}]},{"name":"Education and Teaching Reform Project of Hanshan Normal University","award":["2021KCXTD038","2022KSYS003","2022ZDJS065","PX-161241546"],"award-info":[{"award-number":["2021KCXTD038","2022KSYS003","2022ZDJS065","PX-161241546"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>In this paper, we introduce an efficient and effective algorithm for Graph-based Semi-Supervised Learning (GSSL). Unlike other GSSL methods, our proposed algorithm achieves efficiency by constructing a bipartite graph, which connects a small number of representative points to a large volume of raw data by capturing their underlying manifold structures. This bipartite graph, with a sparse and anti-diagonal affinity matrix which is symmetrical, serves as a low-rank approximation of the original graph. Consequently, our algorithm accelerates both the graph construction and label propagation steps. In particular, on the one hand, our algorithm computes the label propagation in closed-form, reducing its computational complexity from cubic to approximately linear with respect to the number of data points; on the other hand, our algorithm calculates the soft label matrix for unlabeled data using a closed-form solution, thereby gaining additional acceleration. Comprehensive experiments performed on six real-world datasets demonstrate the efficiency and effectiveness of our algorithm in comparison to five state-of-the-art algorithms.<\/jats:p>","DOI":"10.3390\/sym16101312","type":"journal-article","created":{"date-parts":[[2024,10,4]],"date-time":"2024-10-04T12:02:20Z","timestamp":1728043340000},"page":"1312","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Semi-Supervised Learning with Close-Form Label Propagation Using a Bipartite Graph"],"prefix":"10.3390","volume":"16","author":[{"given":"Zhongxing","family":"Peng","sequence":"first","affiliation":[{"name":"School of Computer Information Engineering, Hanshan Normal University, Chaozhou 521041, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gengzhong","family":"Zheng","sequence":"additional","affiliation":[{"name":"School of Computer Information Engineering, Hanshan Normal University, Chaozhou 521041, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Computer Information Engineering, Hanshan Normal University, Chaozhou 521041, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,10,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/978-3-319-10605-2_28","article-title":"Binary Codes Embedding for Fast Image Tagging with Incomplete Labels","volume":"8690","author":"Fleet","year":"2014","journal-title":"Computer Vision\u2014ECCV 2014"},{"key":"ref_2","unstructured":"Zhu, X., Ghahramani, Z., and Lafferty, J. (2003, January 21\u201324). Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions. Proceedings of the 20th International Conference on Machine Learning (ICML-2003), Washington, DC, USA."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"8174","DOI":"10.1109\/TNNLS.2022.3155478","article-title":"Graph-Based Semi-Supervised Learning: A Comprehensive Review","volume":"34","author":"Song","year":"2023","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_4","first-page":"321","article-title":"Learning with Local and Global Consistency","volume":"16","author":"Zhou","year":"2003","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/s00521-009-0305-8","article-title":"A General Graph-based Semi-supervised Learning with Novel Class Discovery","volume":"19","author":"Nie","year":"2010","journal-title":"Neural Comput. Appl."},{"key":"ref_6","unstructured":"Delalleau, O., Bengio, Y., and Le Roux, N. (2005, January 6\u20138). Efficient Non-Parametric Function Induction in Semi-Supervised Learning. Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics (AISTATS-2005), Savannah, GA, USA."},{"key":"ref_7","unstructured":"Kumar, S., Mohri, M., and Talwalkar, A. (2009, January 16\u201318). Sampling techniques for the Nystrom method. Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS-2009), Clearwater Beach, FL, USA."},{"key":"ref_8","first-page":"1401","article-title":"Large-scale sparsified manifold regularization","volume":"19","author":"Tsang","year":"2006","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Zhu, X., and Lafferty, J. (2005, January 7\u201311). Harmonic mixtures: Combining mixture models and graph-based methods for inductive and scalable semi-supervised learning. Proceedings of the 22nd International Conference on Machine Learning, Bonn, Germany.","DOI":"10.1145\/1102351.1102484"},{"key":"ref_10","unstructured":"Fergus, R., Weiss, Y., and Torralba, A. (2010). Semi-supervised learning in gigantic image colletions. Adv. Neural Inf. Process. Syst., 522\u2013530."},{"key":"ref_11","unstructured":"Liu, W., He, J., and Chang, S. (2010, January 21\u201324). Large Graph Construction for Scalabel Semi-Supervised Learning. Proceedings of the International Conference on Machine Learning (ICML-2010), Haifa, Israel."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2624","DOI":"10.1109\/JPROC.2012.2197809","article-title":"Robust and Scalable Graph-Based Semisupervised Learning","volume":"100","author":"Liu","year":"2012","journal-title":"Proc. IEEE"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"3245","DOI":"10.1109\/TKDE.2020.2968523","article-title":"Fast Semi-Supervised Learning With Optimal Bipartite Graph","volume":"33","author":"He","year":"2021","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_14","first-page":"5257","article-title":"Semi-Supervised Learning via Bipartite Graph Construction with Adaptive Neighbors","volume":"35","author":"Wang","year":"2023","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"36","DOI":"10.47443\/cm.2022.011","article-title":"The m-Bipartite Ramsey Number of the K2,2 Versus K6,6","volume":"5","author":"Rowshan","year":"2022","journal-title":"Contrib. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A Tutorial on Spectral Clustering","volume":"17","author":"Luxburg","year":"2007","journal-title":"Stat. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Springer. [2nd ed.].","DOI":"10.1007\/978-0-387-84858-7"},{"key":"ref_18","unstructured":"Ester, M., Kriegel, H., Sander, J., and Xu, X. (1996, January 2\u20134). A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), Portland, OR, USA."},{"key":"ref_19","unstructured":"Bache, K., and Lichman, M. (2013, November 01). UCI Machine Learning Repository. Available online: https:\/\/archive.ics.uci.edu."},{"key":"ref_20","unstructured":"Anwar, Z., Chua, S., and Mowe, R. (1978). The MPH Cookbook, MPH Distributors (S)."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.cviu.2005.09.012","article-title":"Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories","volume":"106","author":"Li","year":"2007","journal-title":"Comput. Vis. Imagin Underst."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Dueck, D., and Frey, B. (2007, January 14\u201321). Non-metric affinity propagation for unsupervised image categorization. Proceedings of the 2007 IEEE 11th International Conference on Computer Vision, Rio de Janeiro, Brazil.","DOI":"10.1109\/ICCV.2007.4408853"},{"key":"ref_23","unstructured":"Dalal, N., and Triggs, B. (2005, January 20\u201325). Histograms of oriented gradients for human detection. Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201905), San Diego, CA, USA."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1109\/34.291440","article-title":"A database for handwritten text recognition research","volume":"16","author":"Hull","year":"1994","journal-title":"Pattern Anal. Mach. Intell. IEEE Trans."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Chua, T., Tang, J., Hong, R., Li, H., Luo, Z., and Zheng, Y. (2009, January 8\u201310). NUS-WIDE: A Real-World Web Image Database from National University of Singapore. Proceedings of the ACM Conference on Image and Video Retrieval (CIVR\u201909), Santorini Island, Greece.","DOI":"10.1145\/1646396.1646452"},{"key":"ref_26","unstructured":"Huang, J., Kumar, S.R., Mitra, M., Zhu, W.J., and Zabih, R. (1997, January 17\u201319). Image indexing using color correlograms. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Juan, PR, USA."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"2278","DOI":"10.1109\/5.726791","article-title":"Gradient-based learning applied to document recognition","volume":"86","author":"Lecun","year":"1998","journal-title":"Proc. IEEE"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Lampert, C., Nickisch, H., and Harmeling, S. (2009, January 20\u201325). Learning to detect unseen object classes by between-class attribute transfer. Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition, Miami, FL, USA.","DOI":"10.1109\/CVPRW.2009.5206594"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1582","DOI":"10.1109\/TPAMI.2009.154","article-title":"Evaluating Color Descriptors for Object and Scene Recognition","volume":"32","author":"Gevers","year":"2010","journal-title":"Pattern Anal. Mach. Intell. IEEE Trans."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"27:1","DOI":"10.1145\/1961189.1961199","article-title":"LIBSVM: A Library for Support Vector Machines","volume":"2","author":"Chang","year":"2011","journal-title":"ACM Trans. Intell. Syst. Technol."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/16\/10\/1312\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:10:50Z","timestamp":1760112650000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/16\/10\/1312"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,4]]},"references-count":30,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2024,10]]}},"alternative-id":["sym16101312"],"URL":"https:\/\/doi.org\/10.3390\/sym16101312","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2024,10,4]]}}}