{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:11:48Z","timestamp":1779174708743,"version":"3.51.4"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science and Technology Major Project","doi-asserted-by":"publisher","award":["2020AAA0108503"],"award-info":[{"award-number":["2020AAA0108503"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSFC Grants","award":["U2241211 and 62072034"],"award-info":[{"award-number":["U2241211 and 62072034"]}]},{"name":"China National Postdoctoral Program for Innovative Talents","award":["BX20240467"],"award-info":[{"award-number":["BX20240467"]}]},{"DOI":"10.13039\/501100006374","name":"China Postdoctoral Science Foundation","doi-asserted-by":"publisher","award":["2023M740245"],"award-info":[{"award-number":["2023M740245"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,10,1]]},"abstract":"<jats:p>\n                    The study of\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -defective cliques, defined as induced subgraphs that differ from cliques by at most\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    missing edges, has attracted much attention in graph analysis due to their relevance in various applications, including social network analysis and implicit interaction predictions. However, determining the maximum\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -defective clique in graphs has been proven to be an NP-hard problem, presenting significant challenges in finding an efficient solution. To address this problem, we develop a theoretically and practically efficient algorithm that leverages newly-designed branch reduction rules and a pivot-based branching technique. Our analysis establishes that the time complexity of the proposed algorithm is bounded by O(m\u03b3\n                    <jats:sub>k<\/jats:sub>\n                    <jats:sup>n<\/jats:sup>\n                    ), where \u03b3\n                    <jats:sub>k<\/jats:sub>\n                    is a real value strictly less than 2 (e.g., when k= 1, 2, and 3, \u03b3\n                    <jats:sub>k<\/jats:sub>\n                    = 1.466, 1.755, and 1.889, respectively). To our knowledge, this algorithm achieves the best worst-case time complexity to date compared to state-of-the-art solutions. Moreover, to further reduce unnecessary branches, we propose a time-efficient upper bound-based pruning technique, which is obtained by manipulating information such as the number of distinct colors assigned to vertices and the presence of non-neighbors among them. Additionally, we employ an ordering-based heuristic approach as a preprocessing step to improve computational efficiency. Finally, we conduct extensive experiments on a diverse set of over 300 graphs to evaluate the efficiency of the proposed solutions. The results demonstrate that our algorithm achieves a speedup of 3 orders of magnitude over state-of-the-art solutions in processing most of real-world graphs.\n                  <\/jats:p>","DOI":"10.1145\/3677142","type":"journal-article","created":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T17:41:44Z","timestamp":1727718104000},"page":"1-27","source":"Crossref","is-referenced-by-count":7,"title":["Theoretically and Practically Efficient Maximum Defective Clique Search"],"prefix":"10.1145","volume":"2","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":"Ronghua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4519-6227","authenticated-orcid":false,"given":"Donghang","family":"Cui","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":[[2024,9,30]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"15","article-title":"Managing Uncertainty in Social Networks","volume":"30","author":"Adar Eytan","year":"2007","unstructured":"Eytan Adar and Christopher R\u00e9. 2007. Managing Uncertainty in Social Networks. IEEE Data Eng. Bull., Vol. 30, 2 (2007), 15--22.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8462-3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"e_1_2_1_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_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1178"},{"key":"e_1_2_1_6_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_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.01.027"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Immanuel M. Bomze Marco Budinich Panos M. Pardalos and Marcello Pelillo. 1999. The Maximum Clique Problem. In Handbook of Combinatorial Optimization. 1--74.","DOI":"10.1007\/978-1-4757-3023-4_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00602-z"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617313"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565817"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105131"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588931"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1348549.1348552"},{"key":"e_1_2_1_16_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\u00f6ffler, 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_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Jian Gao Jiejiang Chen Minghao Yin Rong Chen and Yiyuan Wang. 2018. An Exact Algorithm for Maximum k-Plexes in Massive Graphs. In IJCAI. 1449--1455.","DOI":"10.24963\/ijcai.2018\/201"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","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. In AAAI. 10174--10183.","DOI":"10.1609\/aaai.v36i9.21257"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.09.039"},{"key":"e_1_2_1_21_1","volume-title":"Tur\u00e1n Shadow: PEANUTS. In WWW. 1966--1976.","author":"Jain Shweta","year":"2020","unstructured":"Shweta Jain and C. Seshadhri. 2020. Provably and Efficiently Approximating Near-cliques using the Tur\u00e1n Shadow: PEANUTS. In WWW. 1966--1976."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Hua Jiang Dongming Zhu Zhichao Xie Shaowen Yao and Zhang-Hua Fu. 2021. A New Upper Bound Based on Vertex Partitioning for the Maximum K-plex Problem. In IJCAI. 1689--1696.","DOI":"10.24963\/ijcai.2021\/233"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Richard M. Karp. 1972. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations. 85--103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Ravi Kumar Prabhakar Raghavan Sridhar Rajagopalan Dandapani Sivakumar Andrew Tompkins and Eli Upfal. 2000. The Web as a graph. In PODS. 1--10.","DOI":"10.1145\/335168.335170"},{"key":"e_1_2_1_25_1","volume-title":"Doig","author":"Land Ailsa H.","year":"2010","unstructured":"Ailsa H. Land and Alison G. Doig. 2010. An Automatic Method for Solving Discrete Programming Problems. In 50 Years of Integer Programming 1958--2008 - From the Early Years to the State-of-the-Art. 105--132."},{"key":"e_1_2_1_26_1","volume-title":"A Guide to Graph Colouring - Algorithms and Applications","author":"Lewis R. M. R.","unstructured":"R. M. R. Lewis. 2016. A Guide to Graph Colouring - Algorithms and Applications. Springer."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2017.02.017"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Chu-Min Li Zhiwen Fang and Ke Xu. 2013. Combining MaxSAT reasoning and incremental upper bound for the maximum clique problem. In ICTAI. 939--946.","DOI":"10.1109\/ICTAI.2013.143"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Chu Min Li and Zhe Quan. 2010. An Efficient Branch-and-Bound Algorithm Based on MaxSAT for the Maximum Clique Problem. In AAAI. 128--133.","DOI":"10.1609\/aaai.v24i1.7536"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1970-125-1"},{"key":"e_1_2_1_31_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_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289199"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289146"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.02.003"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9338-2"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2019.0922"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00139635"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-011-9391-5"},{"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","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-012-1242-y"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01098364"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21791"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.07.019"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-0857-4_5"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.10.021"},{"key":"e_1_2_1_46_1","volume-title":"Phizicky and Stanley Fields","author":"Eric","year":"1995","unstructured":"Eric M. Phizicky and Stanley Fields. 1995. Protein-protein interactions: methods for detection and analysis. Microbiological reviews, Vol. 59, 1 (1995), 94--123."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1111\/itor.12637"},{"key":"e_1_2_1_48_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. 4292--4293."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/14100018X"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.07.013"},{"key":"e_1_2_1_51_1","volume-title":"Network structure and minimum degree. Social networks","author":"Seidman Stephen B","year":"1983","unstructured":"Stephen B Seidman. 1983. Network structure and minimum degree. Social networks, Vol. 5, 3 (1983), 269--287."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-006-9039-7"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjjip.25.667"},{"key":"e_1_2_1_55_1","first-page":"191","article-title":"A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique","volume":"5942","author":"Tomita Etsuji","year":"2010","unstructured":"Etsuji Tomita, Yoichi Sutani, Takanori Higashi, Shinya Takahashi, and Mitsuo Wakatsuki. 2010. A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique. In WALCOM, Vol. 5942. 191--203.","journal-title":"WALCOM"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.015"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-013-9548-5"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-015-9804-y"},{"key":"e_1_2_1_59_1","unstructured":"G\u00e9rard Verfaillie Michel Lema^itre and Thomas Schiex. 1996. Russian Doll Search for Solving Constraint Optimization Problems. In AAAI. 181--187."},{"key":"e_1_2_1_60_1","volume-title":"Recent advances in clustering methods for protein interaction networks. BMC genomics","author":"Wang Jianxin","year":"2010","unstructured":"Jianxin Wang, Min Li, Youping Deng, and Yi Pan. 2010. Recent advances in clustering methods for protein interaction networks. BMC genomics, Vol. 11, 3 (2010), 1--19."},{"key":"e_1_2_1_61_1","doi-asserted-by":"crossref","unstructured":"Mingyu Xiao Weibo Lin Yuanshun Dai and Yifeng Zeng. 2017. A Fast Algorithm to Compute Maximum k-Plexes in Social Network Analysis. In AAAI. 919--925.","DOI":"10.1609\/aaai.v31i1.10655"},{"key":"e_1_2_1_62_1","doi-asserted-by":"crossref","unstructured":"Mihalis Yannakakis. 1978. Node- and Edge-Deletion NP-Complete Problems. In STOC. 253--264.","DOI":"10.1145\/800133.804355"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl014"},{"key":"e_1_2_1_64_1","doi-asserted-by":"crossref","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. In AAAI. 12453--12460.","DOI":"10.1609\/aaai.v35i14.17477"},{"key":"e_1_2_1_65_1","doi-asserted-by":"crossref","unstructured":"David Zuckerman. 2006. Linear degree extractors and the inapproximability of max clique and chromatic number. In STOC. 681--690.","DOI":"10.1145\/1132516.1132612"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677142","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3677142","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:11:42Z","timestamp":1774977102000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677142"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,30]]},"references-count":65,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,1]]}},"alternative-id":["10.1145\/3677142"],"URL":"https:\/\/doi.org\/10.1145\/3677142","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,30]]}}}