{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:57:57Z","timestamp":1781326677026,"version":"3.54.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,9,22]]},"abstract":"<jats:p>\n                    Clique enumeration, including maximal clique enumeration and\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -clique enumeration, is a fundamental problem in graph analysis. However, existing clique enumeration algorithms often struggle to efficiently handle complex real-world graphs. To address this issue, we propose a novel Core Clique Removal (CCR) technique that removes a large core clique from the original graph. After removing the core clique, the remaining graph is expected to become sparser. We show that the clique enumeration problem on the original graph can be reduced to the problem of enumerating cliques in the remaining sparser graph, thus reducing computational complexity. Building upon the CCR technique, we propose two innovative and efficient algorithms: CCRMCE for maximal clique enumeration and CCRKCE for\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -clique enumeration. Both algorithms are non-trivial and offer substantial improvements over previous approaches. Our extensive experiments on 20 real-world graphs highlight the efficiency of our methods. CCRMCE demonstrates multiple times faster performance, while CCRKCE achieves an order of magnitude speedup compared to state-of-the-art algorithms.\n                  <\/jats:p>","DOI":"10.1145\/3749187","type":"journal-article","created":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T17:17:03Z","timestamp":1758647823000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["The Power of Core Clique Removal for Exact Clique Enumeration"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0982-341X","authenticated-orcid":false,"given":"Xiaowei","family":"Ye","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3105-5325","authenticated-orcid":false,"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0181-8379","authenticated-orcid":false,"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"International Conference on Research Trends in Science and Technology. 1-10","author":"Abu-Khzam Faisal N","year":"2005","unstructured":"Faisal N Abu-Khzam, Nicole E Baldwin, Michael A Langston, and Nagiza F Samatova. 2005. On the relative efficiency of maximal clique enumeration algorithms, with applications to high-throughput computational biology. In International Conference on Research Trends in Science and Technology. 1-10."},{"key":"e_1_2_1_2_1","first-page":"162","article-title":"Parallelizing Maximal Clique Enumeration on GPUs","author":"Almasri Mohammad","year":"2023","unstructured":"Mohammad Almasri, Yen-Hsiang Chang, Izzat El Hajj, Rakesh Nagi, Jinjun Xiong, and Wen-mei W. Hwu. 2023. Parallelizing Maximal Clique Enumeration on GPUs. In PACT. IEEE, 162-175.","journal-title":"PACT. IEEE"},{"key":"e_1_2_1_3_1","volume-title":"cs.DS\/0310049","author":"Batagelj Vladimir","year":"2003","unstructured":"Vladimir Batagelj and Matjaz Zaversnik. 2003. An O(m) Algorithm for Cores Decomposition of Networks. CoRR, Vol. cs.DS\/0310049 (2003)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSNIP.2013.6529795"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00602-z"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Lijun Chang and Lu Qin. 2019. Cohesive Subgraph Computation Over Large Sparse Graphs. In ICDE.","DOI":"10.1007\/978-3-030-03599-0"},{"key":"e_1_2_1_8_1","first-page":"2544","volume-title":"Maximal Biclique Enumeration: A Prefix Tree Based Approach. In 40th IEEE International Conference on Data Engineering, ICDE 2024","author":"Chen Jiujian","year":"2024","unstructured":"Jiujian Chen, Kai Wang, Ronghua Li, Hongchao Qin, Xuemin Lin, and Guoren Wang. 2024. Maximal Biclique Enumeration: A Prefix Tree Based Approach. In 40th IEEE International Conference on Data Engineering, ICDE 2024, Utrecht, The Netherlands, May 13-16, 2024. IEEE, 2544-2556."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105131"},{"key":"e_1_2_1_10_1","unstructured":"Qihao Cheng Da Yan Tianhao Wu Lyuheng Yuan Ji Cheng Zhongyi Huang and Yang Zhou. 2025. Efficient Enumeration of Large Maximal k-Plexes. In EDBT. OpenProceedings.org 53-65."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.04.003"},{"key":"e_1_2_1_13_1","first-page":"2034","article-title":"Fast Maximal Clique Enumeration on Uncertain Graphs","author":"Dai Qiangqiang","year":"2022","unstructured":"Qiangqiang Dai, Rong-Hua Li, Meihao Liao, Hongzhi Chen, and Guoren Wang. 2022a. Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach. In SIGMOD. ACM, 2034-2047.","journal-title":"A Pivot-based Approach. In SIGMOD. ACM"},{"key":"e_1_2_1_14_1","first-page":"345","article-title":"Scaling Up Maximal k-plex Enumeration","author":"Dai Qiangqiang","year":"2022","unstructured":"Qiangqiang Dai, Rong-Hua Li, Hongchao Qin, Meihao Liao, and Guoren Wang. 2022b. Scaling Up Maximal k-plex Enumeration. ACM, 345-354.","journal-title":"ACM"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589283"},{"key":"e_1_2_1_16_1","unstructured":"Qiangqiang Dai Rong-Hua Li Meihao Liao and Guoren Wang. 2023a. Maximal Defective Clique Enumeration.. In SIGMOD."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Maximilien Danisch Oana Balalau and Mauro Sozio. 2018. Listing k-cliques in Sparse Real-World Graphs. In WWW.","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00540-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3675034.3675036"},{"key":"e_1_2_1_20_1","first-page":"1135","article-title":"Migration motif: a spatial - temporal pattern mining approach for financial markets","author":"Du Xiaoxi","year":"2009","unstructured":"Xiaoxi Du, Ruoming Jin, Liang Ding, Victor E. Lee, and John H. Thornton Jr., 2009. Migration motif: a spatial - temporal pattern mining approach for financial markets. In SIGKDD. ACM, 1135-1144.","journal-title":"SIGKDD. ACM"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2543629"},{"key":"e_1_2_1_22_1","volume-title":"An Exact Algorithm with New Upper Bounds for the Maximum k-Defective Clique Problem in Massive Sparse Graphs","author":"Gao Jian","unstructured":"Jian Gao, Zhenghang Xu, Ruizhi Li, and Minghao Yin. 2022. An Exact Algorithm with New Upper Bounds for the Maximum k-Defective Clique Problem in Massive Sparse Graphs. AAAI Press, 10174-10183."},{"key":"e_1_2_1_23_1","first-page":"721","article-title":"Discovering Large Dense Subgraphs in Massive Graphs","author":"Gibson David","year":"2005","unstructured":"David Gibson, Ravi Kumar, and Andrew Tomkins. 2005. Discovering Large Dense Subgraphs in Massive Graphs. In VLDB. 721-732.","journal-title":"VLDB."},{"key":"e_1_2_1_24_1","first-page":"1587","article-title":"Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions","author":"Han Shuo","year":"2018","unstructured":"Shuo Han, Lei Zou, and Jeffrey Xu Yu. 2018. Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions. In SIGMOD. ACM, 1587-1602.","journal-title":"SIGMOD. ACM"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBME.2003.810689"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Shweta Jain and C. Seshadhri. 2020. The Power of Pivoting for Exact Clique Counting. In WSDM.","DOI":"10.1145\/3336191.3371839"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2021.115915"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0451-4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_2_1_30_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407843"},{"key":"e_1_2_1_32_1","first-page":"641","article-title":"Fast Maximal Clique Enumeration for Real-World Graphs. In DASFAA (Lecture Notes in Computer Science, Vol. 11446)","author":"Li Yinuo","year":"2019","unstructured":"Yinuo Li, Zhiyuan Shao, Dongxiao Yu, Xiaofei Liao, and Hai Jin. 2019. Fast Maximal Clique Enumeration for Real-World Graphs. In DASFAA (Lecture Notes in Computer Science, Vol. 11446). Springer, 641-658.","journal-title":"Springer"},{"key":"e_1_2_1_33_1","volume-title":"Community detection in complex networks via clique conductance. Scientific reports","author":"Lu Zhenqi","year":"2018","unstructured":"Zhenqi Lu, Johan Wahlstr\u00f6m, and Arye Nehorai. 2018. Community detection in complex networks via clique conductance. Scientific reports, Vol. 8, 1 (2018), 5982."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-205"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_36_1","first-page":"824","volume-title":"Science","volume":"298","author":"Milo Ron","year":"2002","unstructured":"Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: simple building blocks of complex networks. Science, Vol. 298, 5594 (2002), 824-827."},{"key":"e_1_2_1_37_1","first-page":"243","article-title":"Mining maximal cliques from an uncertain graph. In ICDE","author":"Mukherjee Arko Provo","year":"2015","unstructured":"Arko Provo Mukherjee, Pan Xu, and Srikanta Tirthapura. 2015. Mining maximal cliques from an uncertain graph. In ICDE, IEEE Computer Society, 243-254.","journal-title":"IEEE Computer Society"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.016"},{"key":"e_1_2_1_40_1","volume-title":"Triangle Listing Algorithms: Back from the Diversion","author":"Ortmann Mark","unstructured":"Mark Ortmann and Ulrik Brandes. 2014. Triangle Listing Algorithms: Back from the Diversion. In ALENEX. SIAM, 1-8."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2024.3441864"},{"key":"e_1_2_1_42_1","volume-title":"Ahmed","author":"Rossi Ryan A.","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/14100018X"},{"key":"e_1_2_1_44_1","unstructured":"Thomas Schank. 2007. Algorithmic Aspects of Triangle-Based Network Analysis. Ph.D. Dissertation. Karlsruhe University Germany."},{"key":"e_1_2_1_45_1","volume-title":"4th InternationalWorkshop, WEA 2005, Santorini Island, Greece, May 10-13, 2005, Proceedings (Lecture Notes in Computer Science","volume":"609","author":"Schank Thomas","year":"2005","unstructured":"Thomas Schank and Dorothea Wagner. 2005. In Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005, Santorini Island, Greece, May 10-13, 2005, Proceedings (Lecture Notes in Computer Science, Vol. 3503). Springer, 606-609."},{"key":"e_1_2_1_46_1","first-page":"115","article-title":"Mining Maximal Cliques on Dynamic Graphs Efficiently by Local Strategies. In ICDE","author":"Sun Shengli","year":"2017","unstructured":"Shengli Sun, Yimo Wang, Weilong Liao, and Wei Wang. 2017. Mining Maximal Cliques on Dynamic Graphs Efficiently by Local Strategies. In ICDE, IEEE Computer Society, 115-118.","journal-title":"IEEE Computer Society"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.015"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639262"},{"key":"e_1_2_1_50_1","first-page":"1517","article-title":"Listing Maximal k-Plexes in Large Real-World Graphs","author":"Wang Zhengren","year":"2022","unstructured":"Zhengren Wang, Yi Zhou, Mingyu Xiao, and Bakhadyr Khoussainov. 2022. Listing Maximal k-Plexes in Large Real-World Graphs. In WWW. 1517-1527.","journal-title":"WWW."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3067053"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2016.2605501"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3232165"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681958"},{"key":"e_1_2_1_55_1","volume-title":"Improving Maximum k-plex Solver via Second-Order Reduction and Graph Color Bounding","author":"Zhou Yi","unstructured":"Yi Zhou, Shan Hu, Mingyu Xiao, and Zhang-Hua Fu. 2021. Improving Maximum k-plex Solver via Second-Order Reduction and Graph Color Bounding. AAAI Press, 12453-12460."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3749187","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:40:24Z","timestamp":1781325624000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3749187"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,22]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,9,22]]}},"alternative-id":["10.1145\/3749187"],"URL":"https:\/\/doi.org\/10.1145\/3749187","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,22]]}}}