{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T21:00:13Z","timestamp":1772226013420,"version":"3.50.1"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T00:00:00Z","timestamp":1628640000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T00:00:00Z","timestamp":1628640000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["1852414-1-1"],"award-info":[{"award-number":["1852414-1-1"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Matrix tri-factorization subject to binary constraints is a versatile and powerful framework for the simultaneous clustering of observations and features, also known as biclustering. Applications for biclustering encompass the clustering of high-dimensional data and explorative data mining, where the selection of the most important features is relevant. Unfortunately, due to the lack of suitable methods for the optimization subject to binary constraints, the powerful framework of biclustering is typically constrained to clusterings which partition the set of observations or features. As a result, overlap between clusters cannot be modelled and every item, even outliers in the data, have to be assigned to exactly one cluster. In this paper we propose<jats:sc>Broccoli<\/jats:sc>, an optimization scheme for matrix factorization subject to binary constraints, which is based on the theoretically well-founded optimization scheme of proximal stochastic gradient descent. Thereby, we do not impose any restrictions on the obtained clusters. Our experimental evaluation, performed on both synthetic and real-world data, and against 6 competitor algorithms, show reliable and competitive performance, even in presence of a high amount of noise in the data. Moreover, a qualitative analysis of the identified clusters shows that<jats:sc>Broccoli<\/jats:sc>may provide meaningful and interpretable clustering structures.<\/jats:p>","DOI":"10.1007\/s10618-021-00787-z","type":"journal-article","created":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T06:03:03Z","timestamp":1628661783000},"page":"2542-2576","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["BROCCOLI: overlapping and outlier-robust biclustering through proximal stochastic gradient descent"],"prefix":"10.1007","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2557-4604","authenticated-orcid":false,"given":"Sibylle","family":"Hess","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2520-3616","authenticated-orcid":false,"given":"Gianvito","family":"Pio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9196-8257","authenticated-orcid":false,"given":"Michiel","family":"Hochstenbach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6690-7583","authenticated-orcid":false,"given":"Michelangelo","family":"Ceci","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,11]]},"reference":[{"key":"787_CR1","unstructured":"Asteris M, Papailiopoulos D, Dimakis AG (2015) Orthogonal NMF through subspace exploration. In: Advances in neural information processing systems, pp 343\u2013351"},{"key":"787_CR2","doi-asserted-by":"crossref","unstructured":"Barracchia EP, Pio G, D\u2019Elia D, Ceci M (2020) Prediction of new associations between NCRNAS and diseases exploiting multi-type hierarchical clustering. BMC Bioinform 21(1):70","DOI":"10.1186\/s12859-020-3392-2"},{"key":"787_CR3","unstructured":"Bauckhage C (2015) K-means clustering is matrix factorization. arXiv preprint arXiv:1512.07548"},{"issue":"1\u20132","key":"787_CR4","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s10107-013-0701-9","volume":"146","author":"J Bolte","year":"2014","unstructured":"Bolte J, Sabach S, Teboulle M (2014) Proximal alternating linearized minimization or nonconvex and nonsmooth problems. Math Program 146(1\u20132):459\u2013494","journal-title":"Math Program"},{"issue":"9","key":"787_CR5","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1016\/j.patcog.2004.03.009","volume":"37","author":"MR Boutell","year":"2004","unstructured":"Boutell MR, Luo J, Shen X, Brown CM (2004) Learning multi-label scene classification. Pattern Recogn 37(9):1757\u20131771","journal-title":"Pattern Recogn"},{"key":"787_CR6","doi-asserted-by":"crossref","unstructured":"Briggs F, Huang Y, Raich R, Eftaxias K, Lei Z, Cukierski W, Hadley SF, Hadley A, Betts M, Fern XZ et\u00a0al (2013) New methods for acoustic classification of multiple simultaneous bird species in a noisy environment. In: 2013 IEEE international workshop on machine learning for signal processing (MLSP), pp 1\u20138","DOI":"10.1109\/MLSP.2013.6661934"},{"issue":"8","key":"787_CR7","doi-asserted-by":"publisher","first-page":"1548","DOI":"10.1109\/TPAMI.2010.231","volume":"33","author":"D Cai","year":"2011","unstructured":"Cai D, He X, Han J, Huang TS (2011) Graph regularized nonnegative matrix factorization for data representation. IEEE Trans Pattern Anal Mach Intell 33(8):1548\u20131560","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"787_CR8","unstructured":"Cheng Y, Church GM (2000) Biclustering of expression data. In: Proceedings of the eighth international conference on intelligent systems for molecular biology, vol 8, pp 93\u2013103"},{"key":"787_CR9","doi-asserted-by":"crossref","unstructured":"Cho H, Dhillon IS, Guan Y, Sra S (2004) Minimum sum-squared residue co-clustering of gene expression data. In: Proceedings of the SIAM international conference on data mining (SDM), pp 114\u2013125","DOI":"10.1137\/1.9781611972740.11"},{"key":"787_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.ins.2014.12.058","volume":"301","author":"N Del Buono","year":"2015","unstructured":"Del Buono N, Pio G (2015) Non-negative matrix tri-factorization for co-clustering: an analysis of the block matrix. Inf Sci 301:13\u201326","journal-title":"Inf Sci"},{"key":"787_CR11","doi-asserted-by":"crossref","unstructured":"Dhillon IS (2001) Co-clustering documents and words using bipartite spectral graph partitioning. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 269\u2013274","DOI":"10.1145\/502512.502550"},{"key":"787_CR12","first-page":"137","volume":"42","author":"C Ding","year":"2006","unstructured":"Ding C, Li T, Peng W (2006a) Nonnegative matrix factorization and probabilistic latent semantic indexing: equivalence chi-square statistic, and a hybrid method. AAAI 42:137\u2013143","journal-title":"AAAI"},{"key":"787_CR13","doi-asserted-by":"crossref","unstructured":"Ding C, Li T, Peng W, Park H (2006b) Orthogonal nonnegative matrix t-factorizations for clustering. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 126\u2013135","DOI":"10.1145\/1150402.1150420"},{"key":"787_CR14","doi-asserted-by":"crossref","unstructured":"Diplaris S, Tsoumakas G, Mitkas PA, Vlahavas I (2005) Protein classification with multiple algorithms. In: Panhellenic conference on informatics, pp 448\u2013456","DOI":"10.1007\/11573036_42"},{"key":"787_CR15","unstructured":"Driggs D, Tang J, Davies M, Sch\u00f6nlieb CB (2020) Spring: a fast stochastic proximal alternating method for non-smooth non-convex optimization. arXiv preprint arXiv:2002.12266"},{"key":"787_CR16","doi-asserted-by":"crossref","unstructured":"Elisseeff A, Weston J (2002) A kernel method for multi-labelled classification. In: Advances in neural information processing systems, pp 681\u2013687","DOI":"10.7551\/mitpress\/1120.003.0092"},{"key":"787_CR17","doi-asserted-by":"crossref","unstructured":"Gaul W, Schader M (1996) A new algorithm for two-mode clustering. In: Data analysis and information systems. Springer, pp 15\u201323","DOI":"10.1007\/978-3-642-80098-6_2"},{"key":"787_CR18","doi-asserted-by":"crossref","unstructured":"Han J, Song K, Nie F, Li X (2017) Bilateral k-means algorithm for fast co-clustering. In: AAAI, pp 1969\u20131975","DOI":"10.1609\/aaai.v31i1.10860"},{"key":"787_CR19","unstructured":"Hardt M, Recht B, Singer Y (2016) Train faster, generalize better: stability of stochastic gradient descent. In: Proceedings of the international conference on machine learning (ICML), pp 1225\u20131234"},{"issue":"337","key":"787_CR20","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1080\/01621459.1972.10481214","volume":"67","author":"JA Hartigan","year":"1972","unstructured":"Hartigan JA (1972) Direct clustering of a data matrix. J Am Stat Assoc 67(337):123\u2013129","journal-title":"J Am Stat Assoc"},{"issue":"4","key":"787_CR21","doi-asserted-by":"publisher","first-page":"1090","DOI":"10.1007\/s10618-017-0508-z","volume":"31","author":"S Hess","year":"2017","unstructured":"Hess S, Morik K, Piatkowski N (2017) The PRIMPING routine\u2014tiling through proximal alternating linearized minimization. Data Min Knowl Discovery (DAMI) 31(4):1090\u20131131","journal-title":"Data Min Knowl Discovery (DAMI)"},{"key":"787_CR22","doi-asserted-by":"publisher","first-page":"1520","DOI":"10.1093\/bioinformatics\/btq227","volume":"26","author":"S Hochreiter","year":"2010","unstructured":"Hochreiter S, Bodenhofer U, Heusel M, Mayr A, Mitterecker A, Kasim A, Khamiakova T, Van Sanden S, Lin D, Talloen W, Bijnens L, G\u00f6hlmann H, Shkedy Z, Clevert DA (2010) Fabia: factor analysis for bicluster acquisition. Bioinformatics (Oxford, England) 26:1520\u20137","journal-title":"Bioinformatics (Oxford, England)"},{"key":"787_CR23","unstructured":"Hoffer E, Hubara I, Soudry D (2017) Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In: Advances in neural information processing systems (NIPS), pp 1731\u20131741"},{"issue":"4","key":"787_CR24","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1101\/gr.648603","volume":"13","author":"Y Kluger","year":"2003","unstructured":"Kluger Y (2003) Spectral biclustering of microarray data: coclustering genes and conditions. Genome Res 13(4):703\u2013716","journal-title":"Genome Res"},{"key":"787_CR25","doi-asserted-by":"crossref","unstructured":"Koyut\u00fcrk M, Grama A (2003) PROXIMUS: a framework for analyzing very high dimensional discrete-attributed datasets. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 147\u2013156","DOI":"10.1145\/956750.956770"},{"issue":"2","key":"787_CR26","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/s10618-018-0597-3","volume":"33","author":"C Laclau","year":"2019","unstructured":"Laclau C, Brault V (2019) Noise-free latent block model for high dimensional data. Data Min Knowl Discovery (DAMI) 33(2):446\u2013473","journal-title":"Data Min Knowl Discovery (DAMI)"},{"key":"787_CR27","doi-asserted-by":"crossref","unstructured":"Li T (2005) A general model for clustering binary data. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery in data mining (KDD), pp 188\u2013197","DOI":"10.1145\/1081870.1081894"},{"issue":"2","key":"787_CR28","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"Lloyd S (1982) Least squares quantization in PCM. IEEE Trans Inf Theory 28(2):129\u2013137","journal-title":"IEEE Trans Inf Theory"},{"key":"787_CR29","doi-asserted-by":"crossref","unstructured":"Long B, Zhang ZM, Yu PS (2005) Co-clustering by block value decomposition, vol \u201905. Association for Computing Machinery, New York, NY, USA, KDD, pp 635\u2013640","DOI":"10.1145\/1081870.1081949"},{"issue":"2","key":"787_CR30","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF03040857","volume":"12","author":"B Mirkin","year":"1995","unstructured":"Mirkin B, Arabie P, Hubert LJ (1995) Additive two-mode clustering: the error-variance approach revisited. J Classif 12(2):243\u2013263","journal-title":"J Classif"},{"key":"787_CR31","unstructured":"Nie F, Wang X, Deng C, Huang H (2017) Learning a structured optimal bipartite graph for co-clustering. In: Advances in neural information processing systems (NIPS), pp 4129\u20134138"},{"issue":"3","key":"787_CR32","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1561\/2400000003","volume":"1","author":"N Parikh","year":"2014","unstructured":"Parikh N, Boyd S et al (2014) Proximal algorithms. Found Trends Optim 1(3):127\u2013239","journal-title":"Found Trends Optim"},{"key":"787_CR33","unstructured":"Pio G, Ceci M, Loglisci C, D\u2019Elia D, Malerba D (2012) Hierarchical and overlapping co-clustering of MRNA: MIRNA interactions. In: ECAI 2012, IOS Press, frontiers in artificial intelligence and applications, vol 242, pp 654\u2013659"},{"key":"787_CR34","doi-asserted-by":"crossref","unstructured":"Pio G, Ceci M, D\u2019Elia D, Loglisci C, Malerba D (2013) A novel biclustering algorithm for the discovery of meaningful biological correlations between micrornas and their target genes. BMC Bioinform 14(S\u20137):S8","DOI":"10.1186\/1471-2105-14-S7-S8"},{"key":"787_CR35","doi-asserted-by":"crossref","unstructured":"Pio G, Ceci M, Malerba D, D\u2019Elia D (2015) Comirnet: a web-based system for the analysis of MIRNA-gene regulatory networks. BMC Bioinform 16(S\u20139):S7","DOI":"10.1186\/1471-2105-16-S9-S7"},{"key":"787_CR36","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.neucom.2014.02.018","volume":"141","author":"F Pompili","year":"2014","unstructured":"Pompili F, Gillis N, Absil PA, Glineur F (2014) Two algorithms for orthogonal nonnegative matrix factorization with application to clustering. Neurocomputing 141:15\u201325","journal-title":"Neurocomputing"},{"issue":"5","key":"787_CR37","doi-asserted-by":"publisher","first-page":"1458","DOI":"10.1007\/s10618-015-0426-x","volume":"29","author":"R Rabbany","year":"2015","unstructured":"Rabbany R, Za\u00efane OR (2015) Generalization of clustering agreements and distances for overlapping clusters and network communities. Data Min Knowl Disc 29(5):1458\u20131485","journal-title":"Data Min Knowl Disc"},{"key":"787_CR38","doi-asserted-by":"publisher","first-page":"107560","DOI":"10.1016\/j.patcog.2020.107560","volume":"109","author":"K Song","year":"2020","unstructured":"Song K, Yao X, Nie F, Li X, Xu M (2020) Weighted bilateral k-means algorithm for fast co-clustering and fast spectral clustering. Pattern Recognit 109:107560","journal-title":"Pattern Recognit"},{"key":"787_CR39","first-page":"325","volume":"8","author":"K Trohidis","year":"2008","unstructured":"Trohidis K, Tsoumakas G, Kalliris G, Vlahavas IP (2008) Multi-label classification of music into emotions. ISMIR 8:325\u2013330","journal-title":"ISMIR"},{"key":"787_CR40","doi-asserted-by":"crossref","unstructured":"Vichi M (2001) Double k-means clustering for simultaneous classification of objects and variables. In: Advances in classification and data analysis, pp 43\u201352","DOI":"10.1007\/978-3-642-59471-7_6"},{"key":"787_CR41","unstructured":"Wang H, Nie F, Huang H, Makedon F (2011) Fast nonnegative matrix tri-factorization for large-scale data co-clustering. In: Proceedings of the international joint conference on artificial intelligence (IJCAI), p 1553"},{"issue":"9","key":"787_CR42","doi-asserted-by":"publisher","first-page":"2620","DOI":"10.1109\/TCYB.2017.2747400","volume":"48","author":"J Wang","year":"2018","unstructured":"Wang J, Tian F, Yu H, Liu CH, Zhan K, Wang X (2018) Diverse non-negative matrix factorization for multiview data representation. IEEE Trans. Cybern. 48(9):2620\u20132632","journal-title":"IEEE Trans. Cybern."},{"key":"787_CR43","doi-asserted-by":"crossref","unstructured":"Whang JJ, Dhillon IS (2017) Non-exhaustive, overlapping co-clustering. In: Proceedings of the ACM conference on information and knowledge management (CIKM), pp 2367\u20132370","DOI":"10.1145\/3132847.3133078"},{"key":"787_CR44","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1142\/S0218213005002387","volume":"14","author":"J Yang","year":"2005","unstructured":"Yang J, Wang H, Wang W, Yu P (2005) An improved biclustering method for analyzing gene expression profiles. Int J Artif Intell Tools 14:771\u2013790","journal-title":"Int J Artif Intell Tools"},{"key":"787_CR45","doi-asserted-by":"crossref","unstructured":"Yokota T, Kawai K, Sakata M, Kimura Y, Hontani H (2019) Dynamic pet image reconstruction using nonnegative matrix factorization incorporated with deep image prior. In: Proceedings of the IEEE\/CVF international conference on computer vision (ICCV)","DOI":"10.1109\/ICCV.2019.00322"},{"issue":"5","key":"787_CR46","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1016\/j.ipm.2009.12.007","volume":"46","author":"J Yoo","year":"2010","unstructured":"Yoo J, Choi S (2010) Orthogonal nonnegative matrix tri-factorization for co-clustering: multiplicative updates on Stiefel manifolds. Inf Process Manag 46(5):559\u2013570","journal-title":"Inf Process Manag"},{"key":"787_CR47","doi-asserted-by":"crossref","unstructured":"Zha H, He X, Ding C, Simon H, Gu M (2001) Bipartite graph partitioning and data clustering. In: Proceedings of the international conference on information and knowledge management, pp 25\u201332","DOI":"10.2172\/816202"},{"key":"787_CR48","doi-asserted-by":"crossref","unstructured":"Zhang Z, Li T, Ding C, Zhang X (2007) Binary matrix factorization with applications. In: IEEE International conference on data mining (ICDM), pp 391\u2013400","DOI":"10.1109\/ICDM.2007.99"},{"issue":"1","key":"787_CR49","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/s10618-009-0145-2","volume":"20","author":"ZY Zhang","year":"2010","unstructured":"Zhang ZY, Li T, Ding C, Ren XW, Zhang XS (2010) Binary matrix factorization for analyzing gene expression data. Data Min. Knowl. Discov (DAMI) 20(1):28","journal-title":"Data Min. Knowl. Discov (DAMI)"},{"issue":"6","key":"787_CR50","doi-asserted-by":"publisher","first-page":"062803","DOI":"10.1103\/PhysRevE.87.062803","volume":"87","author":"ZY Zhang","year":"2013","unstructured":"Zhang ZY, Wang Y, Ahn YY (2013) Overlapping community detection in complex networks using symmetric binary matrix factorization. Phys Rev E 87(6):062803","journal-title":"Phys Rev E"},{"key":"787_CR51","doi-asserted-by":"crossref","unstructured":"Zhou J, Qi J (2011) Fast iterative image reconstruction using sparse matrix factorization with GPU acceleration. In: Progress in biomedical optics and imaging\u2014proceedings of SPIE 7961","DOI":"10.1117\/12.878799"},{"key":"787_CR52","doi-asserted-by":"crossref","unstructured":"Zhou X, Leonardos S, Hu X, Daniilidis K (2015) 3d shape estimation from 2d landmarks: A convex relaxation approach. In: proceedings of the IEEE conference on computer vision and pattern recognition, pp 4447\u20134455","DOI":"10.1109\/CVPR.2015.7299074"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-021-00787-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-021-00787-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-021-00787-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T07:05:40Z","timestamp":1725606340000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-021-00787-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,11]]},"references-count":52,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["787"],"URL":"https:\/\/doi.org\/10.1007\/s10618-021-00787-z","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,11]]},"assertion":[{"value":"22 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}