{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T01:24:17Z","timestamp":1768353857899,"version":"3.49.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T00:00:00Z","timestamp":1720483200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T00:00:00Z","timestamp":1720483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"PNRR Future AI Research (FAIR) project, spoke 9","award":["H23C22000860006, M4C21.3"],"award-info":[{"award-number":["H23C22000860006, M4C21.3"]}]},{"name":"PNRR Future AI Research (FAIR) project, spoke 9","award":["H23C22000860006, M4C21.3"],"award-info":[{"award-number":["H23C22000860006, M4C21.3"]}]},{"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":["Mach Learn"],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p><jats:italic>Signed graphs<\/jats:italic> are a model to depict friendly (<jats:italic>positive<\/jats:italic>) or antagonistic (<jats:italic>negative<\/jats:italic>) interactions (edges) among users (nodes). <jats:sc>2-Polarized-Communities<\/jats:sc> (<jats:sc>2pc<\/jats:sc>) is a well-established combinatorial-optimization problem whose goal is to find two <jats:italic>polarized<\/jats:italic> communities from a signed graph, i.e., two subsets of nodes (disjoint, but not necessarily covering the entire node set) which exhibit a high number of both intra-community positive edges and negative inter-community edges. The state of the art in <jats:sc>2pc<\/jats:sc> suffers from the limitations that (<jats:italic>i<\/jats:italic>) existing methods rely on a single (optimal) solution to a continuous relaxation of the problem in order to produce the ultimate discrete solution via rounding, and (<jats:italic>ii<\/jats:italic>) <jats:sc>2pc<\/jats:sc> objective function comes with no control on size balance among communities. In this paper, we provide advances to the <jats:sc>2pc<\/jats:sc> problem by addressing both these limitations, with a twofold contribution. First, we devise a novel neural approach that allows for soundly and elegantly explore a variety of suboptimal solutions to the relaxed <jats:sc>2pc<\/jats:sc> problem, so as to pick the one that leads to the best discrete solution after rounding. Second, we introduce a generalization of <jats:sc>2pc<\/jats:sc> objective function \u2013 termed <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\gamma $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b3<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-<jats:italic>polarity <\/jats:italic>\u2013 which fosters size balance among communities, and we incorporate it into the proposed machine-learning framework. Extensive experiments attest high accuracy of our approach, its superiority over the state of the art, and capability of function <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\gamma $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b3<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-polarity to discover high-quality size-balanced communities.<\/jats:p>","DOI":"10.1007\/s10994-024-06581-4","type":"journal-article","created":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T17:08:46Z","timestamp":1720544926000},"page":"6611-6644","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Neural discovery of balance-aware polarized communities"],"prefix":"10.1007","volume":"113","author":[{"given":"Francesco","family":"Gullo","sequence":"first","affiliation":[]},{"given":"Domenico","family":"Mandaglio","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Tagarelli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,9]]},"reference":[{"issue":"2","key":"6581_CR1","first-page":"406","volume":"9","author":"AK Ghoshal","year":"2021","unstructured":"Ghoshal, A. K., Das, N., & Das, S. (2021). Disjoint and overlapping community detection in small-world networks leveraging mean path length. TCSS, 9(2), 406\u2013418.","journal-title":"TCSS"},{"key":"6581_CR2","doi-asserted-by":"crossref","unstructured":"Ghoshal, A.K., & Das, N. (2017). On diameter based community structure identification in networks. In Proceedings of the 18th International Conference on Distributed Computing and Networking (pp. 1\u20136).","DOI":"10.1145\/3007748.3018285"},{"key":"6581_CR3","doi-asserted-by":"crossref","unstructured":"Ghoshal, A.K., Das, N., Bhattacharjee, S., & Chakraborty, G. (2019). A fast parallel genetic algorithm based approach for community detection in large networks. In 2019 11th International Conference on Communication Systems & Networks (COMSNETS) (pp. 95\u2013101).","DOI":"10.1109\/COMSNETS.2019.8711127"},{"key":"6581_CR4","doi-asserted-by":"crossref","unstructured":"Conover, M., Ratkiewicz, J., Francisco, M., Goncalves, B., Menczer, F., & Flammini, A. (2011). Political polarization on Twitter. In: Proc. ICWSM Conf., pp. 89\u201396","DOI":"10.1609\/icwsm.v5i1.14126"},{"key":"6581_CR5","doi-asserted-by":"crossref","unstructured":"Hohmann, M., Devriendt, K., & Coscia, M. (2023). Quantifying ideological polarization on a network using generalized Euclidean distance. Science Advances 9(9)","DOI":"10.1126\/sciadv.abq2044"},{"key":"6581_CR6","doi-asserted-by":"crossref","unstructured":"Garimella, K., De\u00a0Francisci\u00a0Morales, G., Gionis, A., & Mathioudakis, M. (2017). Reducing controversy by connecting opposing views. In: Proc. WSDM Conf., pp. 81\u201390","DOI":"10.1145\/3018661.3018703"},{"issue":"S1","key":"6581_CR7","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1093\/poq\/nfw005","volume":"80","author":"Y Lelkes","year":"2016","unstructured":"Lelkes, Y. (2016). Mass polarization: Manifestations and measurements. Public Opinion Quarterly, 80(S1), 392\u2013410.","journal-title":"Public Opinion Quarterly"},{"key":"6581_CR8","doi-asserted-by":"crossref","unstructured":"Bonchi, F., Galimberti, E., Gionis, A., Ordozgoiti, B., & Ruffo, G. (2019). Discovering polarized communities in signed networks. In: Proc. CIKM Conf., pp. 961\u2013970","DOI":"10.1145\/3357384.3357977"},{"key":"6581_CR9","first-page":"10974","volume":"33","author":"R-C Tzeng","year":"2020","unstructured":"Tzeng, R.-C., Ordozgoiti, B., & Gionis, A. (2020). Discovering conflicting groups in signed networks. Proc. NIPS Conf., 33, 10974\u201310985.","journal-title":"Proc. NIPS Conf."},{"key":"6581_CR10","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1307\/mmj\/1028989917","volume":"2","author":"F Harary","year":"1953","unstructured":"Harary, F. (1953). On the notion of balance of a signed graph. Michigan Mathematical Journal, 2, 143\u2013146.","journal-title":"Michigan Mathematical Journal"},{"key":"6581_CR11","doi-asserted-by":"crossref","unstructured":"Beigi, G., Tang, J., & Liu, H. (2016). Signed link analysis in social media networks. In: Proc. ICWSM Conf., pp. 539\u2013542","DOI":"10.1609\/icwsm.v10i1.14793"},{"key":"6581_CR12","doi-asserted-by":"crossref","unstructured":"Derr, T., Aggarwal, C.C., Tang, J. (2018). Signed network modeling based on structural balance theory. In: Proc. CIKM Conf., pp. 557\u2013566","DOI":"10.1145\/3269206.3271746"},{"key":"6581_CR13","doi-asserted-by":"crossref","unstructured":"Yao, K., Chang, L., & Qin, L. (2022). Computing maximum structural balanced cliques in signed graphs. In: Proc. ICDE Conf., pp. 1004\u20131016","DOI":"10.1109\/ICDE53745.2022.00080"},{"issue":"5","key":"6581_CR14","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1007\/s10796-014-9483-8","volume":"17","author":"X Zheng","year":"2015","unstructured":"Zheng, X., Zeng, D. D., & Wang, F. (2015). Social balance in signed networks. Inf. Syst. Frontiers, 17(5), 1077\u20131095.","journal-title":"Inf. Syst. Frontiers"},{"issue":"9","key":"6581_CR15","first-page":"1616","volume":"30","author":"H Cai","year":"2018","unstructured":"Cai, H., Zheng, V. W., & Chang, K. C. (2018). A comprehensive survey of graph embedding: Problems, techniques, and applications. TKDE, 30(9), 1616\u20131637.","journal-title":"TKDE"},{"key":"6581_CR16","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1007\/978-981-16-6054-2","volume-title":"Graph Neural Networks: Foundations, Frontiers, and Applications","author":"L Wu","year":"2022","unstructured":"Wu, L., Cui, P., Pei, J., & Zhao, L. (2022). Graph Neural Networks: Foundations, Frontiers, and Applications (p. 725). Singapore: Springer."},{"key":"6581_CR17","doi-asserted-by":"crossref","unstructured":"Derr, T., Ma, Y., & Tang, J. (2018). Signed graph convolutional networks. In: Proc. ICDM Conf., pp. 929\u2013934","DOI":"10.1109\/ICDM.2018.00113"},{"key":"6581_CR18","doi-asserted-by":"crossref","unstructured":"Liu, H., Zhang, Z., Cui, P., Zhang, Y., Cui, Q., Liu, J., & Zhu, W. (2021). Signed graph neural network with latent groups. In: Proc. KDD Conf., pp. 1066\u20131075","DOI":"10.1145\/3447548.3467355"},{"key":"6581_CR19","doi-asserted-by":"crossref","unstructured":"Li, Y., Tian, Y., Zhang, J., & Chang, Y. (2020). Learning signed network embedding via graph attention. In: Proc. AAAI Conf., pp. 4772\u20134779","DOI":"10.1609\/aaai.v34i04.5911"},{"key":"6581_CR20","doi-asserted-by":"crossref","unstructured":"Wang, S., Tang, J., Aggarwal, C., Chang, Y., & Liu, H. (2017). Signed network embedding in social media. In: Proc. SDM Conf., pp. 327\u2013335","DOI":"10.1137\/1.9781611974973.37"},{"key":"6581_CR21","doi-asserted-by":"crossref","unstructured":"Kim, J., Park, H., Lee, J.-E., & Kang, U. (2018). Side: representation learning in signed directed networks. In: Proc. WWW Conf., pp. 509\u2013518","DOI":"10.1145\/3178876.3186117"},{"key":"6581_CR22","doi-asserted-by":"crossref","unstructured":"Huang, J., Shen, H., Hou, L., & Cheng, X. (2021). SDGNN: learning node representation for signed directed networks. In: Proc. AAAI Conf., pp. 196\u2013203","DOI":"10.1609\/aaai.v35i1.16093"},{"key":"6581_CR23","doi-asserted-by":"crossref","unstructured":"Huang, J., Shen, H., Hou, L., & Cheng, X. (2019). Signed graph attention networks. In: Proc. ICANN Work., pp. 566\u2013577","DOI":"10.1007\/978-3-030-30493-5_53"},{"key":"6581_CR24","doi-asserted-by":"crossref","unstructured":"Chiang, K.-Y., Whang, J.J., & Dhillon, I.S. (2012). Scalable clustering of signed networks using balance normalized cut. In: Proc. CIKM Conf., pp. 615\u2013624","DOI":"10.1145\/2396761.2396841"},{"key":"6581_CR25","unstructured":"Cucuringu, M., Davies, P., Glielmo, A., & Tyagi, H. (2019). SPONGE: A generalized eigenproblem for clustering signed networks. In: Proc. AISTATS Conf., pp. 1088\u20131098"},{"key":"6581_CR26","doi-asserted-by":"crossref","unstructured":"He, Y., Reinert, G., Wang, S., Cucuringu, M. (2022). SSSNET: semi-supervised signed network clustering. In: Proc. SDM Conf., pp. 244\u2013252","DOI":"10.1137\/1.9781611977172.28"},{"key":"6581_CR27","doi-asserted-by":"crossref","unstructured":"Kunegis, J., Schmidt, S., Lommatzsch, A., Lerner, J., Luca, E.W.D., Albayrak, S. (2010). Spectral analysis of signed graphs for clustering, prediction and visualization. In: Proc. SDM Conf., pp. 559\u2013570","DOI":"10.1137\/1.9781611972801.49"},{"key":"6581_CR28","unstructured":"Mercado, P., Tudisco, F., & Hein, M. (2016). Clustering signed networks with the geometric mean of laplacians. In: Proc. NIPS Conf., pp. 4421\u20134429"},{"key":"6581_CR29","doi-asserted-by":"crossref","unstructured":"Ordozgoiti, B., Matakos, A., & Gionis, A. (2020). Finding large balanced subgraphs in signed networks. In: Proc. WWW Conf., pp. 1378\u20131388","DOI":"10.1145\/3366423.3380212"},{"key":"6581_CR30","doi-asserted-by":"crossref","unstructured":"Xiao, H., Ordozgoiti, B., Gionis, A. (2020). Searching for polarization in signed graphs: a local spectral approach. In: Proc. WWW Conf., pp. 362\u2013372","DOI":"10.1145\/3366423.3380121"},{"key":"6581_CR31","doi-asserted-by":"crossref","unstructured":"Niu, J., & Sariy\u00fcce, A.E. (2023). On cohesively polarized communities in signed networks. In: Proc. WWW Conf., pp. 1339\u20131347","DOI":"10.1145\/3543873.3587698"},{"key":"6581_CR32","doi-asserted-by":"crossref","unstructured":"Chu, L., Wang, Z., Pei, J., Wang, J., Zhao, Z., & Chen, E. (2016). Finding gangs in war from signed networks. In: Proc. KDD Conf., pp. 1505\u20131514","DOI":"10.1145\/2939672.2939855"},{"key":"6581_CR33","first-page":"130","volume":"24","author":"Q Cappart","year":"2023","unstructured":"Cappart, Q., Ch\u00e9telat, D., Khalil, E. B., Lodi, A., Morris, C., & Velickovic, P. (2023). Combinatorial optimization and reasoning with graph neural networks. JMLR, 24, 130\u2013113061.","journal-title":"JMLR"},{"issue":"2","key":"6581_CR34","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s41019-021-00155-3","volume":"6","author":"Y Peng","year":"2021","unstructured":"Peng, Y., Choi, B., & Xu, J. (2021). Graph learning for combinatorial optimization: A survey of state-of-the-art. Data Sci. Eng., 6(2), 119\u2013141.","journal-title":"Data Sci. Eng."},{"issue":"3","key":"6581_CR35","first-page":"1288","volume":"10","author":"H Li","year":"2023","unstructured":"Li, H., Xu, M., Bhowmick, S. S., Joty, S. R., Sun, C., & Cui, J. (2023). PIANO: influence maximization meets deep reinforcement learning. TCSS, 10(3), 1288\u20131300.","journal-title":"TCSS"},{"key":"6581_CR36","doi-asserted-by":"crossref","unstructured":"Jung, S., & Keuper, M. (2022). Learning to solve minimum cost multicuts efficiently using edge-weighted graph convolutional neural networks. In: Proc. ECML PKDD Conf., pp. 485\u2013501","DOI":"10.1007\/978-3-031-26390-3_28"},{"key":"6581_CR37","first-page":"1","volume":"24","author":"A Tsitsulin","year":"2023","unstructured":"Tsitsulin, A., Palowitch, J., Perozzi, B., & M\u00fcller, E. (2023). Graph clustering with graph neural networks. JMLR, 24, 1\u201321.","journal-title":"JMLR"},{"key":"6581_CR38","unstructured":"Su, X., Xue, S., Liu, F., Wu, J., Yang, J., Zhou, C., Hu, W., Paris, C., Nepal, S., Jin, D., Sheng, Q.Z., & Yu, P.S (2022). A comprehensive survey on community detection with deep learning. TNNLS, 1\u201321"},{"key":"6581_CR39","unstructured":"Leskovec, J., & Krevl, A. (2014). SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data"},{"key":"6581_CR40","doi-asserted-by":"crossref","unstructured":"Kunegis, J. (2013). KONECT \u2013 The Koblenz Network Collection. In: Proc. WWW Conf., pp. 1343\u20131350. http:\/\/konect.cc","DOI":"10.1145\/2487788.2488173"},{"key":"6581_CR41","doi-asserted-by":"crossref","unstructured":"Lai, M., Patti, V., Ruffo, G., & Rosso, P. (2018). Stance evolution and twitter interactions in an Italian political debate. In: Proc. NLDB Conf., pp. 15\u201327","DOI":"10.1007\/978-3-319-91947-8_2"},{"issue":"1","key":"6581_CR42","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. Machine Learning, 56(1), 89\u2013113.","journal-title":"Machine Learning"},{"key":"6581_CR43","doi-asserted-by":"crossref","unstructured":"Charikar M. (2003). Greedy approximation algorithms for finding dense components in a graph. In: Proc. APPROX Work., pp. 84\u201395","DOI":"10.1007\/3-540-44436-X_10"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-024-06581-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-024-06581-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-024-06581-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T17:32:42Z","timestamp":1723051962000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-024-06581-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,9]]},"references-count":43,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["6581"],"URL":"https:\/\/doi.org\/10.1007\/s10994-024-06581-4","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,9]]},"assertion":[{"value":"20 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests as defined by Springer, or other interests that might be perceived to influence the results and\/or discussion reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"We declare that this research did not require Ethics approval.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"All the authors of this manuscript consent to its publication.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}