{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:35Z","timestamp":1750306835575,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,12,1]],"date-time":"2013-12-01T00:00:00Z","timestamp":1385856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001457","name":"Media Development Authority - Singapore","doi-asserted-by":"publisher","award":["R-252-300-001-490"],"award-info":[{"award-number":["R-252-300-001-490"]}],"id":[{"id":"10.13039\/501100001457","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Multimedia Comput. Commun. Appl."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>With the popularity of photo-sharing websites, the number of web images has exploded into unseen magnitude. Annotating such large-scale data will cost huge amount of human resources and is thus unaffordable. Motivated by this challenging problem, we propose a novel sparse graph based multilabel propagation (SGMP) scheme for super large scale datasets. Both the efficacy and accuracy of the image annotation are further investigated under different graph construction strategies, where Gaussian noise and non-Gaussian sparse noise are simultaneously considered in the formulations of these strategies. Our proposed approach outperforms the state-of-the-art algorithms by focusing on: (1) For large-scale graph construction, a simple yet efficient LSH (<jats:italic>Locality Sensitive Hashing<\/jats:italic>)-based sparse graph construction scheme is proposed to speed up the construction. We perform the multilabel propagation on this hashing-based graph construction, which is derived with LSH approach followed by sparse graph construction within the individual hashing buckets; (2) To further improve the accuracy, we propose a novel sparsity induced scalable graph construction scheme, which is based on a general sparse optimization framework. Sparsity essentially implies a very strong prior: for large scale optimization, the values of most variables shall be zeros when the solution reaches the optimum. By utilizing this prior, the solutions of large-scale sparse optimization problems can be derived by solving a series of much smaller scale subproblems; (3) For multilabel propagation, different from the traditional algorithms that propagate over individual label independently, our proposed propagation first encodes the label information of an image as a unit label confidence vector and naturally imposes inter-label constraints and manipulates labels interactively. Then, the entire propagation problem is formulated on the concept of Kullback-Leibler divergence defined on probabilistic distributions, which guides the propagation of the supervision information. Extensive experiments on the benchmark dataset NUS-WIDE with 270k images and its lite version NUS-WIDE-LITE with 56k images well demonstrate the effectiveness and scalability of the proposed multi-label propagation scheme.<\/jats:p>","DOI":"10.1145\/2542205.2542209","type":"journal-article","created":{"date-parts":[[2014,1,2]],"date-time":"2014-01-02T13:09:43Z","timestamp":1388668183000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Large-scale multilabel propagation based on efficient sparse graph construction"],"prefix":"10.1145","volume":"10","author":[{"given":"Xiangyu","family":"Chen","sequence":"first","affiliation":[{"name":"National University of Singapore and Institute for Infocomm Research, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yadong","family":"Mu","sequence":"additional","affiliation":[{"name":"Columbia University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hairong","family":"Liu","sequence":"additional","affiliation":[{"name":"Purdue University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuicheng","family":"Yan","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong","family":"Rui","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia, Beijing, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tat-Seng","family":"Chua","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,12,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327494"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273501"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Boyd S. and Vandenberghe L. 2004. Convex Optimization. Cambridge University Press. Boyd S. and Vandenberghe L. 2004. Convex Optimization. Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958473.1958487"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"volume-title":"Proceedings of the SIAM International Conference on Data Mining.","author":"Chen G.","key":"e_1_2_2_7_1","unstructured":"Chen , G. , Song , Y. , Wang , F. , and Zhang , C . 2008. Semi-supervised multi-label learning by solving a sylvester equation . In Proceedings of the SIAM International Conference on Data Mining. Chen, G., Song, Y., Wang, F., and Zhang, C. 2008. Semi-supervised multi-label learning by solving a sylvester equation. In Proceedings of the SIAM International Conference on Data Mining."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450037906X"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1873951.1873959"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2009.2038764"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1646396.1646452"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1248547.1248609"},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Cover T. M. and Thomas J. A. 1991. Elements of Information Theory. Wiley Series in Telecommunications. Cover T. M. and Thomas J. A. 1991. Elements of Information Theory. Wiley Series in Telecommunications.","DOI":"10.1002\/0471200611"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics. 96--103","author":"Delalleau O.","year":"2005","unstructured":"Delalleau , O. , Bengio , Y. , and Le Roux , N. 2005 . Efficient non-parametric function induction in semi-supervised learning . In Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics. 96--103 . Delalleau, O., Bengio, Y., and Le Roux, N. 2005. Efficient non-parametric function induction in semi-supervised learning. In Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics. 96--103."},{"key":"e_1_2_2_16_1","unstructured":"Duda R. Stork D. and Hart P. 2000. Pattern Classification. Wiley. Duda R. Stork D. and Hart P. 2000. Pattern Classification. Wiley."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2011.2170081"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/070698920"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Hiriart-Urruty J. and Lemar\u00e9chal C. 2001. Fundamentals of Convex Analysis. Springer-Verlag. Hiriart-Urruty J. and Lemar\u00e9chal C. 2001. Fundamentals of Convex Analysis. Springer-Verlag.","DOI":"10.1007\/978-3-642-56468-0"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML).","author":"Joachims T.","year":"2003","unstructured":"Joachims , T. 2003 . Transductive learning via spectral graph partitioning . In Proceedings of the International Conference on Machine Learning (ICML). Joachims, T. 2003. Transductive learning via spectral graph partitioning. In Proceedings of the International Conference on Machine Learning (ICML)."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390213"},{"volume-title":"Proceedings of NIPS.","author":"Lee H.","key":"e_1_2_2_23_1","unstructured":"Lee , H. , Battle , A. , Raina , R. , and Ng , A . 2007. Efficient sparse coding algorithms . In Proceedings of NIPS. Lee, H., Battle, A., Raina, R., and Ng, A. 2007. Efficient sparse coding algorithms. In Proceedings of NIPS."},{"volume-title":"Proceedings of UAI.","author":"Liu J.","key":"e_1_2_2_24_1","unstructured":"Liu , J. , Ji , S. , and Ye , J . 2009. Multi-task feature learning via efficient l2, 11-norm minimization . In Proceedings of UAI. Liu, J., Ji, S., and Ye, J. 2009. Multi-task feature learning via efficient l2, 11-norm minimization. In Proceedings of UAI."},{"volume-title":"Proceedings of AAAI.","author":"Liu Y.","key":"e_1_2_2_25_1","unstructured":"Liu , Y. , Jin , R. , and Yang , L . 2006. Semi-supervised multi-label learning by constrained non-negative matrix factorization . In Proceedings of AAAI. Liu, Y., Jin, R., and Yang, L. 2006. Semi-supervised multi-label learning by constrained non-negative matrix factorization. In Proceedings of AAAI."},{"volume-title":"Proceedings of CVPR.","author":"Mu Y.","key":"e_1_2_2_26_1","unstructured":"Mu , Y. , Shen , J. , and Yan , S . 2010. Weakly-supervised hashing in kernel space . In Proceedings of CVPR. Mu, Y., Shen, J., and Yan, S. 2010. Weakly-supervised hashing in kernel space. In Proceedings of CVPR."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33718-5_30"},{"key":"e_1_2_2_28_1","article-title":"Grafting: Fast, incremental feature selection by gradient descent in function space","author":"Perkins S.","year":"2003","unstructured":"Perkins , S. , Lacker , K. , and Theiler , J. 2003 . Grafting: Fast, incremental feature selection by gradient descent in function space . J. Mech. Learn. Res. Perkins, S., Lacker, K., and Theiler, J. 2003. Grafting: Fast, incremental feature selection by gradient descent in function space. J. Mech. Learn. Res.","journal-title":"J. Mech. Learn. Res."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291233.1291245"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.290.5500.2323"},{"key":"e_1_2_2_31_1","volume-title":"Artificial Intelligence: A Modern Approach","author":"Russell S.","year":"2009","unstructured":"Russell , S. and Norvig , P . 2009 . Artificial Intelligence: A Modern Approach . Prentice Hall . Russell, S. and Norvig, P. 2009. Artificial Intelligence: A Modern Approach. Prentice Hall."},{"key":"e_1_2_2_32_1","volume-title":"E., Friedlander, M.","author":"Schmidt M.","year":"2009","unstructured":"Schmidt , M. , Van Den Berg , E., Friedlander, M. , and Murphy, K. 2009 . Optimizing costly functions with simple constraints: A limited-memory projected quasi-newton algorithm. In Proceedings of UAI. Schmidt, M., Van Den Berg, E., Friedlander, M., and Murphy, K. 2009. Optimizing costly functions with simple constraints: A limited-memory projected quasi-newton algorithm. In Proceedings of UAI."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148253"},{"volume-title":"Proceedings of EMNLP.","author":"Subramanya A.","key":"e_1_2_2_34_1","unstructured":"Subramanya , A. and Bilmes , J . 2008. Soft-supervised learning for text classification . In Proceedings of EMNLP. Subramanya, A. and Bilmes, J. 2008. Soft-supervised learning for text classification. In Proceedings of EMNLP."},{"volume-title":"Proceedings of NIPS.","author":"Subramanya A.","key":"e_1_2_2_35_1","unstructured":"Subramanya , A. and Bilmes , J . 2009. Entropic graph regularization in non-parametric semi-supervised classification . In Proceedings of NIPS. Subramanya, A. and Bilmes, J. 2009. Entropic graph regularization in non-parametric semi-supervised classification. In Proceedings of NIPS."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1631272.1631305"},{"key":"e_1_2_2_37_1","doi-asserted-by":"crossref","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","article-title":"Regression shrinkage and selection via the lasso","author":"Tibshirani R.","year":"1996","unstructured":"Tibshirani , R. 1996 . Regression shrinkage and selection via the lasso . J. Roy. Stat. Soc. Ser. B (Methodological). Tibshirani, R. 1996. Regression shrinkage and selection via the lasso. J. Roy. Stat. Soc. Ser. B (Methodological).","journal-title":"J. Roy. Stat. Soc. Ser. B (Methodological)."},{"volume-title":"Proceedings of NIPS.","author":"Tsang I. W.","key":"e_1_2_2_38_1","unstructured":"Tsang , I. W. and Kwok , J. T . 2006. Large-scale sparsified manifold regularization . In Proceedings of NIPS. Tsang, I. W. and Kwok, J. T. 2006. Large-scale sparsified manifold regularization. In Proceedings of NIPS."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/080714488"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143968"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10. 1109\/TCSVT.2009.2017400"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvcir.2008.11.009"},{"key":"e_1_2_2_43_1","volume-title":"-S","author":"Zhang H.","year":"2012","unstructured":"Zhang , H. , Zha , Z.-J. , Yan , S. , Wang , M. , and Chua , T . -S . 2012 . Robust non-negative graph embedding: Towards noisy data, unreliable graphs, and noisy labels. In Proceedings of CVPR. Zhang, H., Zha, Z.-J., Yan, S., Wang, M., and Chua, T.-S. 2012. Robust non-negative graph embedding: Towards noisy data, unreliable graphs, and noisy labels. In Proceedings of CVPR."},{"volume-title":"Semi-Supervised Learning with Graphs","author":"Zhu X.","key":"e_1_2_2_44_1","unstructured":"Zhu , X. 2005. Semi-Supervised Learning with Graphs . Carnegie Mellon University . Zhu, X. 2005. Semi-Supervised Learning with Graphs. Carnegie Mellon University."},{"volume-title":"Semi-Supervised Learning Literature Survey","author":"Zhu X.","key":"e_1_2_2_45_1","unstructured":"Zhu , X. 2006. Semi-Supervised Learning Literature Survey . Carnegie Mellon University . Zhu, X. 2006. Semi-Supervised Learning Literature Survey. Carnegie Mellon University."},{"volume-title":"Proceedings of the International Conference on Machine Learning (ICML).","author":"Zhu X.","key":"e_1_2_2_46_1","unstructured":"Zhu , X. , Ghahramani , Z. , and Lafferty , J . 2003. Semi-supervised learning using Gaussian fields and harmonic functions . In Proceedings of the International Conference on Machine Learning (ICML). Zhu, X., Ghahramani, Z., and Lafferty, J. 2003. Semi-supervised learning using Gaussian fields and harmonic functions. In Proceedings of the International Conference on Machine Learning (ICML)."}],"container-title":["ACM Transactions on Multimedia Computing, Communications, and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2542205.2542209","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2542205.2542209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:09:56Z","timestamp":1750234196000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2542205.2542209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1145\/2542205.2542209"],"URL":"https:\/\/doi.org\/10.1145\/2542205.2542209","relation":{},"ISSN":["1551-6857","1551-6865"],"issn-type":[{"type":"print","value":"1551-6857"},{"type":"electronic","value":"1551-6865"}],"subject":[],"published":{"date-parts":[[2013,12]]},"assertion":[{"value":"2011-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}