{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T04:19:42Z","timestamp":1688703582322},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,6,29]],"date-time":"2023-06-29T00:00:00Z","timestamp":1687996800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,29]],"date-time":"2023-06-29T00:00:00Z","timestamp":1687996800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007069","name":"Universit\u00e0 della Calabria","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007069","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2023,7]]},"abstract":"Abstract<\/jats:title>Given a graph whose edges are assigned positive-type and negative-type weights, the problem of correlation clustering<\/jats:italic> aims at grouping the graph vertices so as to minimize (resp. maximize) the sum of negative-type (resp. positive-type) intra-cluster weights plus the sum of positive-type (resp. negative-type) inter-cluster weights. In correlation clustering, it is typically assumed that the weights are readily available. This is a rather strong hypothesis, which is unrealistic in several scenarios. To overcome this limitation, in this work we focus on the setting where edge weights of a correlation-clustering instance are unknown, and they have to be estimated in multiple rounds, while performing the clustering. The clustering solutions produced in the various rounds provide a feedback to properly adjust the weight estimates, and the goal is to maximize the cumulative quality of the clusterings. We tackle this problem by resorting to the reinforcement-learning paradigm, and, specifically, we design for the first time a Combinatorial Multi-Armed Bandit (CMAB) framework for correlation clustering. We provide a variety of contributions, namely (1) formulations of the minimization and maximization variants of correlation clustering in a CMAB setting; (2) adaptation of well-established CMAB algorithms to the correlation-clustering context; (3) regret analyses to theoretically bound the accuracy of these algorithms; (4) design of further (heuristic) algorithms to have the probability constraint satisfied at every round (key condition to soundly adopt efficient yet effective algorithms for correlation clustering as CMAB oracles); (5) extensive experimental comparison among a variety of both CMAB and non-CMAB approaches for correlation clustering.<\/jats:p>","DOI":"10.1007\/s10618-023-00937-5","type":"journal-article","created":{"date-parts":[[2023,6,29]],"date-time":"2023-06-29T12:02:16Z","timestamp":1688040136000},"page":"1630-1691","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A combinatorial multi-armed bandit approach to correlation clustering"],"prefix":"10.1007","volume":"37","author":[{"given":"F.","family":"Gullo","sequence":"first","affiliation":[]},{"given":"D.","family":"Mandaglio","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-8142-503X","authenticated-orcid":false,"given":"A.","family":"Tagarelli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,29]]},"reference":[{"issue":"5","key":"937_CR1","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/1411509.1411513","volume":"55","author":"N Ailon","year":"2008","unstructured":"Ailon N, Charikar M, Newman A (2008) Aggregating inconsistent information: ranking and clustering. JACM 55(5):231\u20132327","journal-title":"JACM"},{"issue":"2\u20133","key":"937_CR2","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1023\/A:1013689704352","volume":"47","author":"P Auer","year":"2002","unstructured":"Auer P, Cesa-Bianchi N, Fischer P (2002) Finite-time analysis of the multiarmed bandit problem. Mach Learn 47(2\u20133):235\u2013256","journal-title":"Mach Learn"},{"issue":"1","key":"937_CR3","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N Bansal","year":"2004","unstructured":"Bansal N, Blum A, Chawla S (2004) Correlation clustering. Mach Learn 56(1):89\u2013113","journal-title":"Mach Learn"},{"key":"937_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-3711-7","volume-title":"Bandit problems: sequential allocation of experiments","author":"DA Berry","year":"1985","unstructured":"Berry DA, Fristedt B (1985) Bandit problems: sequential allocation of experiments. Chapman and Hall, London"},{"issue":"3","key":"937_CR5","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1287\/opre.1030.0083","volume":"52","author":"S Bollapragada","year":"2004","unstructured":"Bollapragada S, Garbiras M (2004) Scheduling commercials on broadcast television. Oper Res 52(3):337\u2013345","journal-title":"Oper Res"},{"key":"937_CR6","doi-asserted-by":"crossref","unstructured":"Bonchi F, Garc\u00eda-Soriano D, Liberty E (2014) Correlation clustering: from theory to practice. In Proceedings of the ACM KDD conference, pp 1972","DOI":"10.1145\/2623330.2630808"},{"key":"937_CR7","doi-asserted-by":"crossref","unstructured":"Bonchi F, Garc\u00eda-Soriano D, Gullo F (2022) Correlation clustering. Synthesis lectures on data mining and knowledge discovery. Morgan & Claypool Publishers","DOI":"10.1007\/978-3-031-79210-6"},{"key":"937_CR8","unstructured":"Bressan M, Cesa-Bianchi N, Paudice A, Vitale F (2019) Correlation clustering with adaptive similarity queries. In: Proceedings of the NIPS conference, pp. 12531\u201312540"},{"issue":"5","key":"937_CR9","first-page":"1404","volume":"78","author":"N Cesa-Bianchi","year":"2012","unstructured":"Cesa-Bianchi N, Lugosi G (2012) Combinatorial bandits. JCSS 78(5):1404\u20131422","journal-title":"JCSS"},{"issue":"3","key":"937_CR10","first-page":"360","volume":"71","author":"M Charikar","year":"2005","unstructured":"Charikar M, Guruswami V, Wirth A (2005) Clustering with qualitative information. JCSS 71(3):360\u2013383","journal-title":"JCSS"},{"key":"937_CR11","doi-asserted-by":"crossref","unstructured":"Chawla S, Makarychev K, Schramm T, Yaroslavtsev G (2015) Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. In: Proceedings of the ACM STOC symposium, pp. 219\u2013228","DOI":"10.1145\/2746539.2746604"},{"key":"937_CR12","unstructured":"Chen L, Xu J, Lu Z (2018) Contextual combinatorial multi-armed bandits with volatile arms and submodular reward. In: Proceedings of the NIPS conference, pp 3251\u20133260"},{"key":"937_CR14","unstructured":"Chen X, Huang W, Chen W, Lui JC (2018b) Community exploration: from offline optimization to online learning. In: Proceedings of the NIPS conference, pp 5474\u20135483"},{"issue":"2\u20133","key":"937_CR15","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.tcs.2006.05.008","volume":"361","author":"ED Demaine","year":"2006","unstructured":"Demaine ED, Emanuel D, Fiat A, Immorlica N (2006) Correlation clustering in general weighted graphs. TCS 361(2\u20133):172\u2013187","journal-title":"TCS"},{"key":"937_CR16","doi-asserted-by":"crossref","unstructured":"Dutta A, Ufimtsev V, Asaithambi A (2019) Correlation clustering based coalition formation for multi-robot task allocation. In: Proceedings of the SAC symposium, pp 906\u2013913","DOI":"10.1145\/3297280.3297369"},{"issue":"1","key":"937_CR17","first-page":"1","volume":"15","author":"E Galimberti","year":"2020","unstructured":"Galimberti E, Ciaperoni M, Barrat A, Bonchi F, Cattuto C, Gullo F (2020) Span-core decomposition for temporal networks: algorithms and applications. ACM Trans Knowl Discov Data (TKDD) 15(1):1\u201344","journal-title":"ACM Trans Knowl Discov Data (TKDD)"},{"key":"937_CR18","doi-asserted-by":"crossref","unstructured":"Garc\u00eda-Soriano D, Kutzkov K, Bonchi F, Tsourakakis C (2020) Query-efficient correlation clustering. In Proceedings of the WWW conference, pp 1468\u20131478","DOI":"10.1145\/3366423.3380220"},{"issue":"4","key":"937_CR19","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1287\/opre.2016.1496","volume":"64","author":"G Giallombardo","year":"2016","unstructured":"Giallombardo G, Jiang H, Miglionico G (2016) New formulations for the conflict resolution problem in the scheduling of television commercials. Oper Res 64(4):838\u2013848","journal-title":"Oper Res"},{"key":"937_CR20","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2022.108110","volume":"169","author":"H Grillo","year":"2022","unstructured":"Grillo H, Alemany M, Caldwell E (2022) Human resource allocation problem in the Industry 4.0: a reference framework. Comput Ind Eng 169:108110","journal-title":"Comput Ind Eng"},{"key":"937_CR21","unstructured":"Gupta A (2005) Lecture notes\u201415-854: approximation algorithms.https:\/\/www.cs.cmu.edu\/afs\/cs\/academic\/class\/15854-f05\/www\/scribe\/lec11.pdf"},{"issue":"301","key":"937_CR22","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding W (1963) Probability inequalities for sums of bounded random variables. JASA 58(301):13\u201330","journal-title":"JASA"},{"issue":"1","key":"937_CR23","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.ejor.2020.10.030","volume":"292","author":"AH H\u00fcbner","year":"2021","unstructured":"H\u00fcbner AH, D\u00fcsterh\u00f6ft T, Ostermeier M (2021) Shelf space dimensioning and product allocation in retail stores. Eur J Oper Res 292(1):155\u2013171","journal-title":"Eur J Oper Res"},{"issue":"7","key":"937_CR24","first-page":"15:31","volume":"54","author":"J Ju\u00e1rez","year":"2022","unstructured":"Ju\u00e1rez J, Santos CP, Brizuela CA (2022) A comprehensive review and a taxonomy proposal of team formation problems. ACM CSUR 54(7):15:31-153:33","journal-title":"ACM CSUR"},{"key":"937_CR25","unstructured":"Kveton B, Szepesv\u00e1ri C, Wen Z, Ashkan A (2015) Cascading bandits: learning to rank in the cascade model. In Proceedings of the ICML conference, pp 767\u2013776"},{"key":"937_CR26","unstructured":"Kveton B, Wen Z, Ashkan A, Szepesv\u00e1ri C (2015) Combinatorial cascading bandits. In: Proceedings of the NIPS conference, pp 1450\u20131458"},{"key":"937_CR27","unstructured":"Lagr\u00e9e P, Vernade C, Capp\u00e9 O (2016) Multiple-play bandits in the position-based model. In: Proceedings of the NIPS conference, pp 1597\u20131605"},{"key":"937_CR28","doi-asserted-by":"crossref","unstructured":"Liu K, Huang H, Zhang W, Hariri A, Fu Y, Hua KA (2021) Multi-armed bandit based feature selection. In: Proceedings of the of SIAM International conference on data mining (SDM), pp 316\u2013323","DOI":"10.1137\/1.9781611976700.36"},{"key":"937_CR29","doi-asserted-by":"crossref","unstructured":"Mandaglio D, Tagarelli A (2019a) A combinatorial multi-armed bandit based method for dynamic consensus community detection in temporal networks. In: Proceedings of the DS conference, pp 412\u2013427","DOI":"10.1007\/978-3-030-33778-0_31"},{"key":"937_CR30","doi-asserted-by":"crossref","unstructured":"Mandaglio D, Tagarelli A (2019b) Dynamic consensus community detection and combinatorial multiarmed bandit. In: Proceedings of the ASONAM conference, pp 184\u2013187","DOI":"10.1145\/3341161.3342910"},{"key":"937_CR31","doi-asserted-by":"crossref","unstructured":"Mandaglio D, Tagarelli A, Gullo F (2020) In and out: optimizing overall interaction in probabilistic graphs under clustering constraints. In: Proceedings of the ACM KDD conference, pp 1371\u20131381","DOI":"10.1145\/3394486.3403190"},{"key":"937_CR32","doi-asserted-by":"crossref","unstructured":"Mandaglio D, Tagarelli A, Gullo F (2021) Correlation clustering with global weight bounds. In: Proceedings of the ECML PKDD conference, pp 499\u2013515","DOI":"10.1007\/978-3-030-86520-7_31"},{"key":"937_CR33","doi-asserted-by":"crossref","unstructured":"Pandove D, Goel S, Rani R (2018) Correlation clustering methodologies and their fundamental results. Expert Syst 35(1)","DOI":"10.1111\/exsy.12229"},{"issue":"3","key":"937_CR34","doi-asserted-by":"publisher","first-page":"1857","DOI":"10.1137\/140994198","volume":"25","author":"GJ Puleo","year":"2015","unstructured":"Puleo GJ, Milenkovic O (2015) Correlation clustering with constrained cluster sizes and extended weights bounds. SIAM J Optim 25(3):1857\u20131872","journal-title":"SIAM J Optim"},{"issue":"1\u20132","key":"937_CR35","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.dam.2004.01.007","volume":"144","author":"R Shamir","year":"2004","unstructured":"Shamir R, Sharan R, Tsur D (2004) Cluster graph modification problems. Discret Appl Math 144(1\u20132):173\u2013182","journal-title":"Discret Appl Math"},{"key":"937_CR36","unstructured":"Swamy C (2004) Correlation clustering: maximizing agreements via semidefinite programming. In: Proceedings of the ACM-SIAM SODA conference, pp 526\u2013527"},{"issue":"4","key":"937_CR37","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1109\/TAC.2017.2747409","volume":"63","author":"MS Talebi","year":"2017","unstructured":"Talebi MS, Zou Z, Combes R, Proutiere A, Johansson M (2017) Stochastic online shortest path routing: the value of feedback. IEEE Trans Autom Control 63(4):915\u2013930","journal-title":"IEEE Trans Autom Control"},{"issue":"21","key":"937_CR38","first-page":"19","volume":"1","author":"M Tomczak","year":"2014","unstructured":"Tomczak M, Tomczak E (2014) The need to report effect size estimates revisited. An overview of some recommended measures of effect size. Trends Sport Sci 1(21):19\u201325","journal-title":"Trends Sport Sci"},{"key":"937_CR39","doi-asserted-by":"crossref","unstructured":"van Zuylen A, Williamson DP (2007) Deterministic algorithms for rank aggregation and other ranking and clustering problems. In: Proceedings of the WAOA work, pp 260\u2013273","DOI":"10.1007\/978-3-540-77918-6_21"},{"key":"937_CR40","unstructured":"Vaswani S, Lakshmanan LVS (2015) Influence maximization with bandits. arXiv:1503.00024"},{"key":"937_CR41","unstructured":"Wang Q, Chen W (2017) Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications. In: Proceedings of the NIPS conference, pp 1161\u20131171"},{"key":"937_CR42","unstructured":"Wang S, Chen W (2018) Thompson sampling for combinatorial semi-bandits. In: Proceedings of the ICML conference, pp 5101\u20135109"},{"key":"937_CR43","doi-asserted-by":"crossref","unstructured":"Wu Q, Li Z, Wang H, Chen W, Wang H (2019) Factorization bandits for online influence maximization. In: Proceedings of the ACM KDD conference, pp 636\u2013646","DOI":"10.1145\/3292500.3330874"},{"key":"937_CR44","doi-asserted-by":"crossref","unstructured":"Xu H, Liu Y, Lau WC, Li R (2020) Combinatorial multi-armed bandits with concave rewards and fairness constraints. In: Proceedings of the IJCAI conference, pp 2554\u20132560","DOI":"10.24963\/ijcai.2020\/354"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-023-00937-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-023-00937-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-023-00937-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T17:16:54Z","timestamp":1688663814000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-023-00937-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,29]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["937"],"URL":"https:\/\/doi.org\/10.1007\/s10618-023-00937-5","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,29]]},"assertion":[{"value":"10 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2023","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 and no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter discussed in this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}