{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:39Z","timestamp":1750306719597,"version":"3.41.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,8,25]],"date-time":"2014-08-25T00:00:00Z","timestamp":1408924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["845951"],"award-info":[{"award-number":["845951"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2014,10,28]]},"abstract":"<jats:p>Boosting is a highly effective algorithm that produces a linear combination of weak classifiers (a.k.a. base learners) to obtain high-quality classification models. In this article, we propose a generalized logit boost algorithm in which base learners have structural relationships in the functional space. Although such relationships are generic, our work is particularly motivated by the emerging topic of pattern-based classification for semistructured data including graphs. Toward an efficient incorporation of the structure information, we have designed a general model in which we use an undirected graph to capture the relationship of subgraph-based base learners. In our method, we employ both<jats:italic>L<\/jats:italic><jats:sub>1<\/jats:sub>and Laplacian-based<jats:italic>L<\/jats:italic><jats:sub>2<\/jats:sub>regularization to logit boosting to achieve model sparsity and smoothness in the functional space spanned by the base learners. We have derived efficient optimization algorithms based on coordinate descent for the new boosting formulation and theoretically prove that it exhibits a natural grouping effect for nearby spatial or overlapping base learners and that the resulting estimator is consistent. Additionally, motivated by the connection between logit boosting and logistic regression, we extend our structured sparse regularization framework to logistic regression for vectorial data in which features are structured. Using comprehensive experimental study and comparing our work with the state-of-the-art, we have demonstrated the effectiveness of the proposed learning method.<\/jats:p>","DOI":"10.1145\/2629328","type":"journal-article","created":{"date-parts":[[2014,8,26]],"date-time":"2014-08-26T12:08:55Z","timestamp":1409054935000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Structured Sparse Boosting for Graph Classification"],"prefix":"10.1145","volume":"9","author":[{"given":"Hongliang","family":"Fei","sequence":"first","affiliation":[{"name":"EECS Department, University of Kansas, Lawrence KS"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Huan","sequence":"additional","affiliation":[{"name":"EECS Department, University of Kansas, Lawrence KS"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8,25]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1016\/j.neuroimage.2012.07.046"},{"doi-asserted-by":"crossref","unstructured":"P. L. Bartlett and M. Traskin. 2006. AdaBoost is consistent. In Advances in Neural Information Processing Systems (NIPS\u201906). 105--112. P. L. Bartlett and M. Traskin. 2006. AdaBoost is consistent. In Advances in Neural Information Processing Systems (NIPS\u201906). 105--112.","key":"e_1_2_1_2_1","DOI":"10.7551\/mitpress\/7503.003.0018"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1002\/prot.10638"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/1961189.1961199"},{"key":"e_1_2_1_5_1","series-title":"CBMS Regional Conferences Series 92","volume-title":"Spectral graph theory","author":"Chung F.","year":"1997","unstructured":"F. Chung . 1997. Spectral graph theory . CBMS Regional Conferences Series 92 ( 1997 ). F. Chung. 1997. Spectral graph theory. CBMS Regional Conferences Series 92 (1997)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/1273496.1273521"},{"doi-asserted-by":"crossref","unstructured":"M. Deshpande M. Kuramochi and G. Karypis. 2005. Frequent sub-structure-based approaches for classifying chemical compounds. IEEE Transactions on Knowledge and Data Engineering (2005). M. Deshpande M. Kuramochi and G. Karypis. 2005. Frequent sub-structure-based approaches for classifying chemical compounds. IEEE Transactions on Knowledge and Data Engineering (2005).","key":"e_1_2_1_7_1","DOI":"10.1109\/TKDE.2005.127"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/1553374.1553412"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/1458082.1458212"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/1645953.1646029"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1006\/inco.1995.1136"},{"volume-title":"Proceedings of the 2nd European Conference on Computational Learning Theory. 23--37","author":"Freund Y.","unstructured":"Y. Freund and R. Shapire . 1995. A decision-theoretic generalization of on-line learning and an application to boosting . In Proceedings of the 2nd European Conference on Computational Learning Theory. 23--37 . Y. Freund and R. Shapire. 1995. A decision-theoretic generalization of on-line learning and an application to boosting. In Proceedings of the 2nd European Conference on Computational Learning Theory. 23--37.","key":"e_1_2_1_12_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1214\/aos\/1016218223"},{"doi-asserted-by":"crossref","unstructured":"J. Friedman T. Hastie and R. Tibshirani. 2009. Regularization paths for generalized linear models via coordinate descent. Journal of Statistical Software 33 (2009). J. Friedman T. Hastie and R. Tibshirani. 2009. Regularization paths for generalized linear models via coordinate descent. Journal of Statistical Software 33 (2009).","key":"e_1_2_1_14_1","DOI":"10.18637\/jss.v033.i01"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1093\/bioinformatics\/btg382"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1371\/journal.pcbi.1002638"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1023\/A:1012487302797"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/1390156.1390203"},{"doi-asserted-by":"crossref","unstructured":"T. Hastie R. Tibshirani and J. Friedman. 2009. The Elements of Statistical Learning. Springer-Verlag. T. Hastie R. Tibshirani and J. Friedman. 2009. The Elements of Statistical Learning. Springer-Verlag.","key":"e_1_2_1_19_1","DOI":"10.1007\/978-0-387-84858-7"},{"volume-title":"Proceedings of the 3rd IEEE International Conference on Data Mining (ICDM\u201903)","author":"Huan J.","unstructured":"J. Huan , W. Wang , and J. Prins . 2003. Efficient mining of frequent subgraph in the presence of isomorphism . In Proceedings of the 3rd IEEE International Conference on Data Mining (ICDM\u201903) . 549--552. J. Huan, W. Wang, and J. Prins. 2003. Efficient mining of frequent subgraph in the presence of isomorphism. In Proceedings of the 3rd IEEE International Conference on Data Mining (ICDM\u201903). 549--552.","key":"e_1_2_1_20_1"},{"unstructured":"L. Jacob F. Bach and J.-P. Vert. 2009. Clustered multi-task learning: A convex formulation. In Neural Information Processing Systems (NIPS). L. Jacob F. Bach and J.-P. Vert. 2009. Clustered multi-task learning: A convex formulation. In Neural Information Processing Systems (NIPS).","key":"e_1_2_1_21_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1109\/ICDE.2011.5767922"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/1645953.1646027"},{"doi-asserted-by":"crossref","unstructured":"R. Jorissen and M. Gilson. 2005. Virtual screening of molecular databases using a support vector machine. Journal of Chemical Information Modeling 45(3) (2005) 549--561. R. Jorissen and M. Gilson. 2005. Virtual screening of molecular databases using a support vector machine. Journal of Chemical Information Modeling 45(3) (2005) 549--561.","key":"e_1_2_1_24_1","DOI":"10.1021\/ci049641u"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1093\/nar\/gkj102"},{"volume-title":"Proceedings of the 20th International Conference on Machine Learning (ICML). 321--328","author":"Kashima H.","unstructured":"H. Kashima , K. Tsuda , and A. Inokuchi . 2003. Marginalized kernels between labeled graphs . In Proceedings of the 20th International Conference on Machine Learning (ICML). 321--328 . H. Kashima, K. Tsuda, and A. Inokuchi. 2003. Marginalized kernels between labeled graphs. In Proceedings of the 20th International Conference on Machine Learning (ICML). 321--328.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","first-page":"1356","article-title":"Asymptotics for lasso-type estimators","volume":"28","author":"Knight K.","year":"2000","unstructured":"K. Knight and W. Fu . 2000 . Asymptotics for lasso-type estimators . Journal of the Royal Statisical Society 28 , 5 (2000), 1356 -- 1378 . K. Knight and W. Fu. 2000. Asymptotics for lasso-type estimators. Journal of the Royal Statisical Society 28, 5 (2000), 1356--1378.","journal-title":"Journal of the Royal Statisical Society"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/1553374.1553443"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1145\/2020408.2020511"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/1835804.1835905"},{"unstructured":"Taku Kudo Eisaku Maeda and Yuji Matsumoto. 2004. An application of boosting to graph classification. In The Neural Information Processing Systems (NIPS\u201904). Taku Kudo Eisaku Maeda and Yuji Matsumoto. 2004. An application of boosting to graph classification. In The Neural Information Processing Systems (NIPS\u201904).","key":"e_1_2_1_31_1"},{"volume-title":"Proceedings of the Pacific Symposium on Biocomputing. 564--75","author":"Leslie C.","unstructured":"C. Leslie , E. Eskin , and W. S. Noble . 2002. The spectrum kernel: A string kernel for SVM protein classification . In Proceedings of the Pacific Symposium on Biocomputing. 564--75 . C. Leslie, E. Eskin, and W. S. Noble. 2002. The spectrum kernel: A string kernel for SVM protein classification. In Proceedings of the Pacific Symposium on Biocomputing. 564--75.","key":"e_1_2_1_32_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1093\/bioinformatics\/btn081"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1145\/1553374.1553455"},{"key":"e_1_2_1_35_1","series-title":"Suppl 6","volume-title":"Mcm-test: A fuzzy-set-theory-based approach to differential analysis of gene pathways. BMC Bioinformatics 9","author":"Liang L.","year":"2008","unstructured":"L. Liang , V. Mandal , Y. Lu , and D. Kumar . 2008 . Mcm-test: A fuzzy-set-theory-based approach to differential analysis of gene pathways. BMC Bioinformatics 9 ( Suppl 6 ) (2008), S16. L. Liang, V. Mandal, Y. Lu, and D. Kumar. 2008. Mcm-test: A fuzzy-set-theory-based approach to differential analysis of gene pathways. BMC Bioinformatics 9 (Suppl 6) (2008), S16."},{"doi-asserted-by":"crossref","unstructured":"C. Liu X. Yan H. Yu J. Han and P. S. Yu. 2005. Mining behavior graphs for \u201cbacktrace\u201d of noncrashing bugs. In SDM. C. Liu X. Yan H. Yu J. Han and P. S. Yu. 2005. Mining behavior graphs for \u201cbacktrace\u201d of noncrashing bugs. In SDM.","key":"e_1_2_1_36_1","DOI":"10.1137\/1.9781611972757.26"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1145\/1390156.1390233"},{"unstructured":"T. M. Mitchell and McGraw Hill. 2010. Chapter 1 of Machine Learning: Generative and Discriminative Classifiers: Naive Bayes and Logistic Regression. Preprint. 12--16 pages. Available at http:\/\/www.cs.cmu.edu\/&sim;tom\/mlbook\/NBayesLogReg.pdf. T. M. Mitchell and McGraw Hill. 2010. Chapter 1 of Machine Learning: Generative and Discriminative Classifiers: Naive Bayes and Logistic Regression. Preprint. 12--16 pages. Available at http:\/\/www.cs.cmu.edu\/&sim;tom\/mlbook\/NBayesLogReg.pdf.","key":"e_1_2_1_38_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1109\/ICTAI.2007.29"},{"key":"e_1_2_1_40_1","volume-title":"Laurila et al","author":"Mootha V.","year":"2003","unstructured":"V. Mootha , C. Lindgren , K. Eriksson , A. Subramanian , S. Sihag , J. Lehar , P. Puigserver , E. Carlsson , M. Ridderstraale , E. Laurila et al . 2003 . PGC-1: A-responsive genes involved in oxidative phosphorylation are coordinately downregulated in human diabetes. Nature Genetics 34, 3 (2003), 267C273. V. Mootha, C. Lindgren, K. Eriksson, A. Subramanian, S. Sihag, J. Lehar, P. Puigserver, E. Carlsson, M. Ridderstraale, E. Laurila et al. 2003. PGC-1: A-responsive genes involved in oxidative phosphorylation are coordinately downregulated in human diabetes. Nature Genetics 34, 3 (2003), 267C273."},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1016\/S0022-2836(05)80134-2"},{"volume-title":"Proceedings of the IEEE Computer Vision and Pattern Recognition (CVPR\u201907)","author":"Nowozin S.","unstructured":"S. Nowozin , K. Tsuda , T. Uno , T. Kudo , and G. Bakir . 2007. Weighted substructure mining for image analysis . In Proceedings of the IEEE Computer Vision and Pattern Recognition (CVPR\u201907) . 1--8. S. Nowozin, K. Tsuda, T. Uno, T. Kudo, and G. Bakir. 2007. Weighted substructure mining for image analysis. In Proceedings of the IEEE Computer Vision and Pattern Recognition (CVPR\u201907). 1--8.","key":"e_1_2_1_42_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1002\/sam.v1:4"},{"unstructured":"H. Saigo et al. 2007. gBoost: Graph Learning Toolbox for Matlab. Available at http:\/\/www.kyb.tuebingen.mpg.de\/bs\/people\/nowozin\/gboost\/. H. Saigo et al. 2007. gBoost: Graph Learning Toolbox for Matlab. Available at http:\/\/www.kyb.tuebingen.mpg.de\/bs\/people\/nowozin\/gboost\/.","key":"e_1_2_1_44_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1145\/1401890.1401961"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.1007\/s10994-008-5089-z"},{"unstructured":"T. Sandler P. P. Talukdar and L. H. Ungar. 2008. Regularized learning with networks of features. In The Neural Information Processing Systems (NIPS). T. Sandler P. P. Talukdar and L. H. Ungar. 2008. Regularized learning with networks of features. In The Neural Information Processing Systems (NIPS).","key":"e_1_2_1_47_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_48_1","DOI":"10.1023\/A:1022648800760"},{"doi-asserted-by":"publisher","key":"e_1_2_1_49_1","DOI":"10.1023\/A:1007614523901"},{"volume-title":"Proceedings of the 2009 SIAM Conference on Data Mining (SDM\u201909)","author":"Thoma M.","unstructured":"M. Thoma , H. Cheng , A. Gretton , J. Han , H.-P. Kriegel , A. J. Smola , L. Song , P. S. Yu , X. Yan , and K. M. Borgwardt . 2009. Near-optimal supervised feature selection among frequent subgraphs . In Proceedings of the 2009 SIAM Conference on Data Mining (SDM\u201909) . Philadelphia, PA, 1076--1087. M. Thoma, H. Cheng, A. Gretton, J. Han, H.-P. Kriegel, A. J. Smola, L. Song, P. S. Yu, X. Yan, and K. M. Borgwardt. 2009. Near-optimal supervised feature selection among frequent subgraphs. In Proceedings of the 2009 SIAM Conference on Data Mining (SDM\u201909). Philadelphia, PA, 1076--1087.","key":"e_1_2_1_50_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_51_1","DOI":"10.1111\/j.1467-9868.2005.00490.x"},{"doi-asserted-by":"publisher","key":"e_1_2_1_52_1","DOI":"10.1145\/1273496.1273612"},{"volume-title":"Proceedings of the Neural Information Processing Systems (NIPS\u201909)","author":"Xiang Z.","unstructured":"Z. Xiang , Y. Xi , U. Hasson , and P. Ramadge . 2009. Boosting with spatial regularization . In Proceedings of the Neural Information Processing Systems (NIPS\u201909) . 2107--2115. Z. Xiang, Y. Xi, U. Hasson, and P. Ramadge. 2009. Boosting with spatial regularization. In Proceedings of the Neural Information Processing Systems (NIPS\u201909). 2107--2115.","key":"e_1_2_1_53_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_54_1","DOI":"10.1145\/1281192.1281281"},{"doi-asserted-by":"publisher","key":"e_1_2_1_55_1","DOI":"10.1145\/1376616.1376662"},{"doi-asserted-by":"publisher","key":"e_1_2_1_56_1","DOI":"10.1111\/j.1467-9868.2005.00532.x"},{"unstructured":"P. Zhao and B. Yu. 2006. Grouped and hierarchical model selection through composite absolute penalties. Annals of Statistics (2006) 3468--3497. P. Zhao and B. Yu. 2006. Grouped and hierarchical model selection through composite absolute penalties. Annals of Statistics (2006) 3468--3497.","key":"e_1_2_1_57_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_58_1","DOI":"10.1109\/ICDM.2011.119"},{"doi-asserted-by":"publisher","key":"e_1_2_1_59_1","DOI":"10.1145\/1557019.1557129"},{"doi-asserted-by":"publisher","key":"e_1_2_1_60_1","DOI":"10.1111\/j.1467-9868.2005.00503.x"},{"key":"e_1_2_1_61_1","first-page":"379","article-title":"F\u221e norm support vector machine","volume":"18","author":"Zou H.","year":"2008","unstructured":"H. Zou and M. Yuan . 2008 . F\u221e norm support vector machine . Statistica Sinica 18 (2008), 379 -- 398 . H. Zou and M. Yuan. 2008. F\u221e norm support vector machine. Statistica Sinica 18 (2008), 379--398.","journal-title":"Statistica Sinica"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629328","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629328","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:30Z","timestamp":1750231170000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629328"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,25]]},"references-count":61,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,10,28]]}},"alternative-id":["10.1145\/2629328"],"URL":"https:\/\/doi.org\/10.1145\/2629328","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2014,8,25]]},"assertion":[{"value":"2013-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}