{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:11:39Z","timestamp":1779174699478,"version":"3.51.4"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSFC Grants","award":["U2241211, 62072034, U1809206"],"award-info":[{"award-number":["U2241211, 62072034, U1809206"]}]},{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2020AAA0108503"],"award-info":[{"award-number":["2020AAA0108503"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"name":"CCF-Huawei Populus Grove Fund"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Maximal clique enumeration is a fundamental operator in graph analysis. The model of clique, however, is typically too restrictive for real-world applications as it requires an edge for every pair of vertices. To remedy this restriction, practical graph analysis applications often resort to find relaxed cliques as alternatives. In this work, we investigate a notable relaxed clique model, called s-defective clique, which allows at most s edges to be missing. Similar to the complexity of maximal clique enumeration, the problem of enumerating all maximal s-defective cliques is also NP-hard. To solve this problem, we first develop a new polynomial-delay algorithm based on a carefully-designed reverse search technique, which can output two consecutive results within polynomial time. To achieve better practical efficiency, we propose a branch-and-bound algorithm with a novel pivoting technique. We prove that the time complexity of this algorithm depends only on O(\u03b1_sn) or O(\u03b1s\u03b4) when using a degeneracy ordering optimization, where \u03b1s is a positive real number strictly less than 2, and \u03b4 (\u03b4 &lt;n) is the degeneracy of the graph. To our knowledge, this is the first algorithm that can break the O(2n) time complexity to enumerate all maximal s-defective cliques (s&gt;0). We also develop several new pruning techniques to further improve the efficiency of our branch-and-bound algorithm to enumerate all relatively-large maximal s-defective cliques. In addition, we further generalize our pivot-based branch-and-bound algorithm to enumerate all maximal subgraphs satisfying a hereditary property. Here we call a graph meeting the hereditary property if all its subgraphs have the same property as itself. Finally, extensive experiments on 11 datasets demonstrate the efficiency, effectiveness, and scalability of the proposed solutions.<\/jats:p>","DOI":"10.1145\/3588931","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-26","source":"Crossref","is-referenced-by-count":18,"title":["Maximal Defective Clique Enumeration"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8569-6558","authenticated-orcid":false,"given":"Qiangqiang","family":"Dai","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8658-6599","authenticated-orcid":false,"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5808-3131","authenticated-orcid":false,"given":"Meihao","family":"Liao","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Aman Abidi Rui Zhou Lu Chen and Chengfei Liu. 2020. Pivot-based Maximal Biclique Enumeration. In IJCAI. 3558--3564.","DOI":"10.24963\/ijcai.2020\/492"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"e_1_2_2_3_1","volume-title":"Bader and Christopher WV Hogue","author":"Gary","year":"2002","unstructured":"Gary D. Bader and Christopher WV Hogue. 2002. Analyzing yeast protein--protein interaction data obtained from different sources. Nature biotechnology, Vol. 20, 10 (2002), 991--997."},{"key":"e_1_2_2_4_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_2_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1178"},{"key":"e_1_2_2_6_1","unstructured":"Rachel Behar and Sara Cohen. 2018. Finding All Maximal Connected s-Cliques in Social Networks. In EDBT. 61--72."},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Devora Berlowitz Sara Cohen and Benny Kimelfeld. 2015. Efficient Enumeration of Maximal k-Plexes. In SIGMOD. 431--444.","DOI":"10.1145\/2723372.2746478"},{"key":"e_1_2_2_8_1","volume-title":"Statistical analysis of financial networks. Computational statistics & data analysis","author":"Boginski Vladimir","year":"2005","unstructured":"Vladimir Boginski, Sergiy Butenko, and Panos M Pardalos. 2005. Statistical analysis of financial networks. Computational statistics & data analysis, Vol. 48, 2 (2005), 431--443."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.01.027"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.05.026"},{"key":"e_1_2_2_12_1","unstructured":"Fr\u00e9d\u00e9ric Cazals and Chinmay Karande. 2006. Reporting maximal cliques: new insights into an old problem. Ph. D. Dissertation. INRIA."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105131"},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Zi Chen Long Yuan Xuemin Lin Lu Qin and Jianye Yang. 2020. Efficient Maximal Balanced Clique Enumeration in Signed Networks. In WWW. 339--349.","DOI":"10.1145\/3366423.3380119"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.04.003"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1152206"},{"key":"e_1_2_2_17_1","volume-title":"Daniele De Sensi, Roberto Grossi, Andrea Marino, and Luca Versari.","author":"Conte Alessio","year":"2018","unstructured":"Alessio Conte, Tiziano De Matteis, Daniele De Sensi, Roberto Grossi, Andrea Marino, and Luca Versari. 2018. D2K: Scalable Community Detection in Massive Networks via Small-Diameter k-Plexes. In KDD. 1272--1281."},{"key":"e_1_2_2_18_1","unstructured":"Qiangqiang Dai Rong-Hua Li Meihao Liao and Guoren Wang. 2023. Maximal Defective Clique Enumeration (full version). https:\/\/github.com\/qq-dai\/DefectiveClique\/blob\/main\/DefectiveClique-full.pdf"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Naga Shailaja Dasari Desh Ranjan and Mohammad Zubair. 2014. pbitMCE: A bit-based approach for maximal clique enumeration on multicore processors. In ICPADS. 478--485.","DOI":"10.1109\/PADSW.2014.7097844"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1348549.1348552"},{"key":"e_1_2_2_21_1","first-page":"403","article-title":"Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time","volume":"6506","author":"Eppstein David","year":"2010","unstructured":"David Eppstein, Maarten L\u00f6 ffler, and Darren Strash. 2010. Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. In ISAAC, Vol. 6506. 403--414.","journal-title":"ISAAC"},{"key":"e_1_2_2_22_1","volume-title":"Exact Exponential Algorithms","author":"Fomin Fedor V.","unstructured":"V. Fomin Fedor and Kratsch Dieter. 2010. Exact Exponential Algorithms. Springer."},{"key":"e_1_2_2_23_1","volume-title":"Nature","volume":"415","author":"Gavin Anne-Claude","year":"2002","unstructured":"Anne-Claude Gavin, Markus B\u00f6sche, Roland Krause, Paola Grandi, Martina Marzioch, Andreas Bauer, J\u00f6rg Schultz, Jens M. Rick, Anne-Marie Michon, Cristina-Maria Cruciat, et al. 2002. Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature, Vol. 415, 6868 (2002), 141--147."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.6.487"},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","unstructured":"Anne-Sophie Himmel Hendrik Molter Rolf Niedermeier and Manuel Sorge. 2016. Enumerating maximal cliques in temporal graphs. In ASONAM. 337--344.","DOI":"10.1109\/ASONAM.2016.7752255"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.243"},{"key":"e_1_2_2_27_1","volume-title":"Community detection algorithms: a comparative analysis. Physical review E","author":"Lancichinetti Andrea","year":"2009","unstructured":"Andrea Lancichinetti and Santo Fortunato. 2009. Community detection algorithms: a comparative analysis. Physical review E., Vol. 80, 5 (2009), 056117."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190660"},{"key":"e_1_2_2_29_1","volume-title":"Jeffrey Xu Yu, and Shaojie Qiao","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 ICDE. 245--256."},{"key":"e_1_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Rong-Hua Li Qiangqiang Dai Guoren Wang Zhong Ming Lu Qin and Jeffrey Xu Yu. 2019. Improved Algorithms for Maximal Clique Search in Uncertain Networks. In ICDE. 1178--1189.","DOI":"10.1109\/ICDE.2019.00108"},{"key":"e_1_2_2_31_1","first-page":"3335","article-title":"I\/O-Efficient Algorithms for Degeneracy Computation on Massive Networks","volume":"34","author":"Li Rong-Hua","year":"2022","unstructured":"Rong-Hua Li, Qiushuo Song, Xiaokui Xiao, Lu Qin, Guoren Wang, Jeffrey Xu Yu, and Rui Mao. 2022. I\/O-Efficient Algorithms for Degeneracy Computation on Massive Networks. IEEE Trans. Knowl. Data Eng., Vol. 34, 7 (2022), 3335--3348.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1970-125-1"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.2021.3071721"},{"key":"e_1_2_2_34_1","first-page":"33","article-title":"Effective Pruning Techniques for Mining Quasi-Cliques","volume":"5212","author":"Liu Guimei","year":"2008","unstructured":"Guimei Liu and Limsoon Wong. 2008. Effective Pruning Techniques for Mining Quasi-Cliques. In ECML\/PKDD, Vol. 5212. 33--49.","journal-title":"ECML\/PKDD"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289199"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760024"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2527643"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.016"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.10.021"},{"key":"e_1_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Jian Pei Daxin Jiang and Aidong Zhang. 2005. On mining cross-graph quasi-cliques. In KDD. 228--238.","DOI":"10.1145\/1081870.1081898"},{"key":"e_1_2_2_42_1","unstructured":"Hongchao Qin Rong-Hua Li Guoren Wang Lu Qin Yurong Cheng and Ye Yuan. 2019. Mining Periodic Cliques in Temporal Networks. In ICDE. 1130--1141."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2017.12.006"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_2_2_46_1","doi-asserted-by":"crossref","unstructured":"Etsuji Tomita Tatsuya Akutsu and Tsutomu Matsunaga. 2011. Efficient algorithms for finding maximum and maximal cliques: Effective tools for bioinformatics. IntechOpen.","DOI":"10.5772\/13245"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.015"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-013-9548-5"},{"key":"e_1_2_2_49_1","doi-asserted-by":"crossref","unstructured":"Zhengren Wang Yi Zhou Mingyu Xiao and Bakhadyr Khoussainov. 2022. Listing Maximal k-Plexes in Large Real-World Graphs. In WWW.","DOI":"10.1145\/3485447.3512198"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl014"},{"key":"e_1_2_2_51_1","doi-asserted-by":"crossref","unstructured":"Kaiqiang Yu Cheng Long Shengxin Liu and Da Yan. 2022. Efficient Algorithms for Maximal k-Biplex Enumeration. In SIGMOD. 860--873.","DOI":"10.1145\/3514221.3517847"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-110"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2021.05.001"},{"key":"e_1_2_2_54_1","doi-asserted-by":"crossref","unstructured":"Yi Zhou Jingwei Xu Zhenyu Guo Mingyu Xiao and Yan Jin. 2020. Enumerating Maximal k-Plexes with Worst-Case Time Guarantee. In AAAI. 2442--2449.","DOI":"10.1609\/aaai.v34i03.5625"},{"key":"e_1_2_2_55_1","doi-asserted-by":"crossref","unstructured":"Zhaonian Zou Jianzhong Li Hong Gao and Shuo Zhang. 2010. Finding top-k maximal cliques in an uncertain graph. In ICDE. 649--652.","DOI":"10.1109\/ICDE.2010.5447891"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588931","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588931","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:37Z","timestamp":1750178857000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588931"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588931"],"URL":"https:\/\/doi.org\/10.1145\/3588931","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}