{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T14:09:20Z","timestamp":1779286160386,"version":"3.51.4"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T00:00:00Z","timestamp":1779235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100014013","name":"UK Research and Innovation","doi-asserted-by":"crossref","award":["EP\/Y036786\/1"],"award-info":[{"award-number":["EP\/Y036786\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"crossref"}]},{"name":"EU Horizon Europe","award":["101129910"],"award-info":[{"award-number":["101129910"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>\n                    Quasi-clique is one of the most fundamental models for characterizing cohesive subgraphs in network analysis. However, existing quasi-clique definitions and identification algorithms are designed for unsigned graphs, while many real-world networks are modeled as signed graphs with positive and negative edges representing cooperative and adversarial interactions between entities. Therefore, it remains an open problem to define a quasi-clique model tailored for signed graphs. Motivated by this, we propose the maximal balanced\n                    <jats:inline-formula>\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(  (\\gamma_{1},\\gamma_{2})  \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -quasi-clique (MBQC) model, which not only preserves the essence of quasi-completeness but also aligns with the foremost structural balance theory for signed graphs. Specifically, we formulate the problem of MBQCs enumeration in a given signed graph and prove its NP-hardness. To address this problem, we devise a novel branch-and-bound algorithm to efficiently enumerate all MBQCs in a signed graph, which is further optimized with several carefully-crafted techniques to prune unpromising search spaces and enhance enumeration efficiency. Extensive experiments on real-world datasets demonstrate the efficiency, scalability, and effectiveness of our MBQC model and algorithms.\n                  <\/jats:p>","DOI":"10.1145\/3806834","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T13:46:06Z","timestamp":1775569566000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximal Balanced Quasi-Clique Enumeration in Signed Graphs"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3542-5389","authenticated-orcid":false,"given":"Jie","family":"Gao","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Exeter, Exeter, United Kingdom of Great Britain and Northern Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5406-8420","authenticated-orcid":false,"given":"Jia","family":"Hu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Exeter, Exeter, United Kingdom of Great Britain and Northern Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5288-5523","authenticated-orcid":false,"given":"Fei","family":"Hao","sequence":"additional","affiliation":[{"name":"School of Artificial Intelligence and Computer Science, Shaanxi Normal University, Xi\u2019an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1395-7314","authenticated-orcid":false,"given":"Geyong","family":"Min","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Exeter, Exeter, United Kingdom of Great Britain and Northern Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4646-2054","authenticated-orcid":false,"given":"Lei","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Software, Shandong University, Jinan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,20]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Vladimir Batagelj and Matjaz Zaversnik. 2003. An \\(O(m)\\) algorithm for cores decomposition of networks. arXiv:cs\/0310049. Retrieved from https:\/\/arxiv.org\/abs\/cs\/0310049"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357977"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684567"},{"key":"e_1_3_3_5_2","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1145\/3637528.3671674","volume-title":"Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","author":"Chen Jingbang","year":"2024","unstructured":"Jingbang Chen, Qiuyang Mang, Hangrui Zhou, Richard Peng, Yu Gao, and Chenhao Ma. 2024. Scalable algorithm for finding balanced subgraphs with tolerance in signed networks. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 278\u2013287."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3690624.3709342"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380119"},{"issue":"11","key":"e_1_3_3_8_2","doi-asserted-by":"crossref","first-page":"11079","DOI":"10.1109\/TKDE.2022.3225562","article-title":"Balanced clique computation in signed networks: Concepts and algorithms","volume":"35","author":"Chen Zi","year":"2022","unstructured":"Zi Chen, Long Yuan, Xuemin Lin, Lu Qin, and Wenjie Zhang. 2022. Balanced clique computation in signed networks: Concepts and algorithms. IEEE Transactions on Knowledge and Data Engineering 35, 11 (2022), 11079\u201311092.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_3_9_2","unstructured":"Matteo Cinelli Gianmarco De Francisci Morales Alessandro Galeazzi Walter Quattrociocchi and Michele Starnini. 2020. Echo chambers on social media: A comparative analysis. arXiv:2004.09603. Retrieved from https:\/\/arxiv.org\/abs\/2004.09603"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3588931"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1177\/001872676702000206"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.14778\/3675034.3675036"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3404835.3463014"},{"key":"e_1_3_3_15_2","first-page":"668","volume-title":"Proceedings of the 2014 SIAM International Conference on Data Mining","author":"Giatsidis Christos","year":"2014","unstructured":"Christos Giatsidis, Bogdan Cautis, Silviu Maniu, Dimitrios M. Thilikos, and Michalis Vazirgiannis. 2014. Quantifying trust dynamics in signed graphs, the S-cores approach. In Proceedings of the 2014 SIAM International Conference on Data Mining. SIAM, 668\u2013676."},{"issue":"4","key":"e_1_3_3_16_2","doi-asserted-by":"crossref","first-page":"573","DOI":"10.14778\/3436905.3436916","article-title":"Scalable mining of maximal quasi-cliques: An algorithm-system codesign approach","volume":"14","author":"Guo Guimu","year":"2020","unstructured":"Guimu Guo, Da Yan, M. Tamer \u00d6zsu, Zhe Jiang, and Jalal Khalil. 2020. Scalable mining of maximal quasi-cliques: An algorithm-system codesign approach. In Proceedings of the VLDB Endowment 14, 4 (2020), 573\u2013585.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_3_17_2","first-page":"1900","volume-title":"Proceedings of the 2022 IEEE 38th International Conference on Data Engineering (ICDE)","author":"Guo Guimu","year":"2022","unstructured":"Guimu Guo, Da Yan, Lyuheng Yuan, Jalal Khalil, Cheng Long, Zhe Jiang, and Yang Zhou. 2022. Maximal directed quasi-clique mining. In Proceedings of the 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 1900\u20131913."},{"key":"e_1_3_3_18_2","unstructured":"Prithwish Jana Romit Roy Choudhury and Niloy Ganguly. 2023. Reducing opinion echo-chambers by intelligent placement of moderate-minded agents. arXiv:2304.10745. Retrieved from https:\/\/arxiv.org\/abs\/2304.10745"},{"key":"e_1_3_3_19_2","first-page":"687","volume-title":"Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","author":"Ji Yingsheng","year":"2022","unstructured":"Yingsheng Ji, Zheng Zhang, Xinlei Tang, Jiachen Shen, Xi Zhang, and Guangwen Yang. 2022. Detecting cash-out users via dense subgraphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 687\u2013697."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00712-2"},{"key":"e_1_3_3_21_2","first-page":"543","volume-title":"Proceedings of the International Conference on Database Systems for Advanced Applications","author":"Kim Junghoon","year":"2022","unstructured":"Junghoon Kim and Sungsu Lim. 2022. (p, n)-core: Core decomposition in signed networks. In Proceedings of the International Conference on Database Systems for Advanced Applications. Springer, 543\u2013551."},{"key":"e_1_3_3_22_2","first-page":"8608","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"38","author":"Konar Aritra","year":"2024","unstructured":"Aritra Konar and Nicholas D. Sidiropoulos. 2024. Optimal quasi-clique: Hardness, equivalence with densest-k-subgraph, and quasi-partitioned community mining. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, 8608\u20138616."},{"key":"e_1_3_3_23_2","first-page":"522","volume-title":"Proceedings of the 2016 SIAM International Conference on Data Mining","author":"Lee Pei","year":"2016","unstructured":"Pei Lee and Laks V. S. Lakshmanan. 2016. Query-driven maximum quasi-clique search. In Proceedings of the 2016 SIAM International Conference on Data Mining. SIAM, 522\u2013530."},{"key":"e_1_3_3_24_2","first-page":"72","volume-title":"Proceedings of the 2008 SIAM International Conference on Data Mining","author":"Li Jinyan","year":"2008","unstructured":"Jinyan Li, Kelvin Sim, Guimei Liu, and Limsoon Wong. 2008. Maximal quasi-bicliques with balanced noise tolerance: Concepts and co-clustering applications. In Proceedings of the 2008 SIAM International Conference on Data Mining. SIAM, 72\u201383."},{"issue":"2","key":"e_1_3_3_25_2","first-page":"710","article-title":"Signed clique search in signed networks: Concepts and algorithms","volume":"33","author":"Li Ronghua","year":"2019","unstructured":"Ronghua Li, Qiangqiang Dai, Lu Qin, Guoren Wang, Xiaokui Xiao, Jeffrey Xu Yu, and Shaojie Qiao. 2019. Signed clique search in signed networks: Concepts and algorithms. IEEE Transactions on Knowledge and Data Engineering 33, 2 (2019), 710\u2013727.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_3_26_2","first-page":"245","volume-title":"Proceedings of the 2018 IEEE 34th International Conference on Data Engineering (ICDE)","author":"Li Rong-Hua","year":"2018","unstructured":"Rong-Hua Li, Qiangqiang Dai, Lu Qin, Guoren Wang, Xiaokui Xiao, Jeffrey Xu Yu, and Shaojie Qiao. 2018. Efficient signed clique search in signed networks. In Proceedings of the 2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE, 245\u2013256."},{"issue":"6","key":"e_1_3_3_27_2","first-page":"3731","article-title":"Mining stable quasi-cliques on temporal networks","volume":"52","author":"Lin Longlong","year":"2021","unstructured":"Longlong Lin, Pingpeng Yuan, Rong-Hua Li, Jifei Wang, Ling Liu, and Hai Jin. 2021. Mining stable quasi-cliques on temporal networks. IEEE Transactions on Systems, Man, and Cybernetics: Systems 52, 6 (2021), 3731\u20133745.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics: Systems"},{"key":"e_1_3_3_28_2","first-page":"33","volume-title":"Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases","author":"Liu Guimei","year":"2008","unstructured":"Guimei Liu and Limsoon Wong. 2008. Effective pruning techniques for mining quasi-cliques. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 33\u201349."},{"issue":"2","key":"e_1_3_3_29_2","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1109\/TCBB.2008.61","article-title":"Modeling protein interacting groups by quasi-bicliques: Complexity, algorithm, and application","volume":"7","author":"Liu Xiaowen","year":"2008","unstructured":"Xiaowen Liu, Jinyan Li, and Lusheng Wang. 2008. Modeling protein interacting groups by quasi-bicliques: Complexity, algorithm, and application. IEEE\/ACM Transactions on Computational Biology and Bioinformatics 7, 2 (2008), 354\u2013364.","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1013213108"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186103"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3543873.3587698"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2015.2401014"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.21791"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081898"},{"issue":"1","key":"e_1_3_3_36_2","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/s13721-024-00470-5","article-title":"DeMoS: Dense module based gene signature detection through quasi-clique: An application to cervical cancer prognosis","volume":"13","author":"Saha Suparna","year":"2024","unstructured":"Suparna Saha, Soumita Seth, Soumadip Ghosh, Guimin Qin, Tapas Bhadra, Soumen Kumar Pati, Somenath Chakraborty, and Saurav Mallik. 2024. DeMoS: Dense module based gene signature detection through quasi-clique: An application to cervical cancer prognosis. Network Modeling Analysis in Health Informatics and Bioinformatics 13, 1 (2024), 36.","journal-title":"Network Modeling Analysis in Health Informatics and Bioinformatics"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3446637"},{"key":"e_1_3_3_38_2","unstructured":"Daniela Scherer dos Santos Kathrin Klamroth Pedro Martins and Lu\u00eds Paquete. 2024. Solving the multiobjective quasi-clique problem. arXiv:2403.10896. Retrieved from https:\/\/arxiv.org\/abs\/2403.10896"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0245122"},{"key":"e_1_3_3_40_2","first-page":"1887","volume-title":"Proceedings of the 2022 IEEE 38th International Conference on Data Engineering (ICDE)","author":"Sun Renjie","year":"2022","unstructured":"Renjie Sun, Yanping Wu, Chen Chen, Xiaoyang Wang, Wenjie Zhang, and Xuemin Lin. 2022. Maximal balanced signed biclique enumeration in signed bipartite graphs. In Proceedings of the 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 1887\u20131899."},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3272636"},{"key":"e_1_3_3_42_2","first-page":"666","volume-title":"Proceedings of the International Conference on Database Systems for Advanced Applications","author":"Sun Renjie","year":"2020","unstructured":"Renjie Sun, Qiuyu Zhu, Chen Chen, Xiaoyang Wang, Ying Zhang, and Xun Wang. 2020. Discovering cliques in signed networks based on balance theory. In Proceedings of the International Conference on Database Systems for Advanced Applications. Springer, 666\u2013674."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.2733"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3417457"},{"key":"e_1_3_3_45_2","unstructured":"Hongbo Xia Kaiqiang Yu Shengxin Liu Cheng Long and Xun Zhou. 2025. Maximum degree-based quasi-clique search via an iterative framework. arXiv:2505.15118. Retrieved from https:\/\/arxiv.org\/abs\/2505.15118"},{"issue":"5","key":"e_1_3_3_46_2","doi-asserted-by":"crossref","first-page":"2587","DOI":"10.1109\/TBDATA.2025.3552335","article-title":"Efficient antagonistic  \\( k \\) -plex enumeration in signed graphs","volume":"11","author":"Xu Lantian","year":"2025","unstructured":"Lantian Xu, Rong-Hua Li, Dong Wen, Qiangqiang Dai, and Guoren Wang. 2025. Efficient antagonistic \\( k \\) -plex enumeration in signed graphs. IEEE Transactions on Big Data 11, 5 (2025), 2587\u20132600.","journal-title":"IEEE Transactions on Big Data"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-020-03646-8"},{"key":"e_1_3_3_48_2","first-page":"1665","volume-title":"Proceedings of the 39th International Conference on Data Engineering (ICDE)","author":"Yin Ziqi","year":"2023","unstructured":"Ziqi Yin, Qi Zhang, Wentao Zhang, Rong-Hua Li, and Guoren Wang. 2023. Fairness-aware maximal biclique enumeration on bipartite graphs. In Proceedings of the 39th International Conference on Data Engineering (ICDE). IEEE, 1665\u20131677."},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3617331"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150506"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10796-014-9483-8"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357966"},{"key":"e_1_3_3_53_2","first-page":"2531","volume-title":"Proceedings of the 2024 IEEE 40th International Conference on Data Engineering (ICDE)","author":"Zhou Alexander","year":"2024","unstructured":"Alexander Zhou, Yue Wang, Lei Chen, and M. Tamer \u00d6zsu. 2024. Positive communities on signed graphs that are not echo chambers: A clique-based approach. In Proceedings of the 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 2531\u20132543."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3806834","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T13:31:25Z","timestamp":1779283885000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3806834"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,20]]},"references-count":52,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3806834"],"URL":"https:\/\/doi.org\/10.1145\/3806834","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,20]]},"assertion":[{"value":"2025-07-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-05-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}