{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:06:56Z","timestamp":1775815616719,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:p>\n            <jats:italic>k<\/jats:italic>\n            -defective clique is a relaxation of the well-studied clique structure, by allowing up-to\n            <jats:italic>k<\/jats:italic>\n            edges missing from a clique. The problem of finding a\n            <jats:italic>k<\/jats:italic>\n            -defective clique with the largest number of vertices, although being NP-hard, has been receiving increasing interests recently, with advancements in both the theoretical time complexity and practical efficiency. The state-of-the-art time complexity is\n            <jats:italic>\n              O*(\u03b3\n              <jats:sup>n<\/jats:sup>\n              <jats:sub>k<\/jats:sub>\n              )\n            <\/jats:italic>\n            , where\n            <jats:italic>O*<\/jats:italic>\n            ignores polynomial factors,\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices in the input graph\n            <jats:italic>G<\/jats:italic>\n            , and\n            <jats:italic>\n              \u03b3\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            &lt; 2 is a constant that only depends on\n            <jats:italic>k.<\/jats:italic>\n            In this paper, we first prove, through a more refined and non-trivial analysis, that the time complexity of an existing algorithm can actually be bounded by\n            <jats:italic>\n              O* (\u03b3\n              <jats:sup>n<\/jats:sup>\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            <jats:sub>-1<\/jats:sub>\n            ), where\n            <jats:italic>\n              \u03b3\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            <jats:sub>-1<\/jats:sub>\n            &lt;\n            <jats:italic>\n              \u03b3\n              <jats:sub>k<\/jats:sub>\n              .\n            <\/jats:italic>\n            Then, by utilizing the diameter-two property of large\n            <jats:italic>k<\/jats:italic>\n            -deffective cliques, we show that for graphs with maximum\n            <jats:italic>k<\/jats:italic>\n            -defective clique sizes\n            <jats:italic>\n              \u03c9\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) \u2265\n            <jats:italic>k<\/jats:italic>\n            + 2, a maximum\n            <jats:italic>k<\/jats:italic>\n            -defective clique can be found in\n            <jats:italic>O*<\/jats:italic>\n            ((\n            <jats:italic>\u03b1<\/jats:italic>\n            \u0394\n            <jats:italic>\n              )\n              <jats:sup>k<\/jats:sup>\n            <\/jats:italic>\n            <jats:sup>+2<\/jats:sup>\n            <jats:italic>\n              \u03b3\n              <jats:sup>\u03b1<\/jats:sup>\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            <jats:sub>-1<\/jats:sub>\n            ) time when using the degeneracy parameterization\n            <jats:italic>\u03b1<\/jats:italic>\n            and in\n            <jats:italic>O<\/jats:italic>\n            ((\u03b1\u0394)\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n              +2\n            <\/jats:sup>\n            \u03b3\n            <jats:sup>\u03b1<\/jats:sup>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n              -1\n            <\/jats:sub>\n            ) time when using the degeneracy-gap parameterization\n            <jats:italic>\u03b1<\/jats:italic>\n            +\n            <jats:italic>k<\/jats:italic>\n            + 1 -\n            <jats:italic>\n              \u03c9\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ); here,\n            <jats:italic>\u03b1<\/jats:italic>\n            and \u0394 are the degeneracy and maximum degree of\n            <jats:italic>G<\/jats:italic>\n            , respectively. Note that, most real graphs satisfy\n            <jats:italic>\n              \u03c9\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) \u2265\n            <jats:italic>k<\/jats:italic>\n            + 2 and\n            <jats:italic>\u03b1<\/jats:italic>\n            \u226a\n            <jats:italic>n.<\/jats:italic>\n            Lastly, to improve the practical performance, we design a new degree-sequence-based reduction rule that can be efficiently applied, and theoretically demonstrate its effectiveness compared with the existing reduction rules. Extensive empirical studies on three benchmark graph collections, containing 290 graphs in total, show that our algorithm is also practically efficient, by outperforming all existing algorithms by several orders of magnitude. We remark that our proving techniques for reducing the base from\n            <jats:italic>\n              \u03b3\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            to\n            <jats:italic>\n              \u03b3\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            <jats:sub>-1<\/jats:sub>\n            and our general principle of designing a new reduction rule may also be beneficial to other problems.\n          <\/jats:p>","DOI":"10.14778\/3705829.3705839","type":"journal-article","created":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:21:06Z","timestamp":1740784866000},"page":"200-212","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance"],"prefix":"10.14778","volume":"18","author":[{"given":"Lijun","family":"Chang","sequence":"first","affiliation":[{"name":"The University of Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,28]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proc. of LATIN'02 (Lecture Notes in Computer Science)","author":"Abello James","unstructured":"James Abello, Mauricio G. C. Resende, and Sandra Sudarsky. 2002. Massive Quasi-Clique Detection. In Proc. of LATIN'02 (Lecture Notes in Computer Science), Vol. 2286. Springer, 598--612."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2015.01.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1178"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(01)00133-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(90)90057-C"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330986"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617313"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3682032"},{"key":"e_1_2_1_10_1","series-title":"Springer Series in the Data Sciences","volume-title":"Cohesive Subgraph Computation over Large Sparse Graphs","author":"Chang Lijun","unstructured":"Lijun Chang and Lu Qin. 2018. Cohesive Subgraph Computation over Large Sparse Graphs. Springer Series in the Data Sciences."},{"key":"e_1_2_1_11_1","volume-title":"Jeffrey Xu Yu, and Lu Qin","author":"Chang Lijun","year":"2012","unstructured":"Lijun Chang, Jeffrey Xu Yu, and Lu Qin. 2012. Fast Maximal Cliques Enumeration in Sparse Graphs. Algorithmica (2012)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105131"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043652.2043654"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588931"},{"key":"e_1_2_1_15_1","volume-title":"Listing All Maximal Cliques in Large Sparse Real-World Graphs. ACM Journal of Experimental Algorithmics 18","author":"Eppstein David","year":"2013","unstructured":"David Eppstein, Maarten L\u00f6ffler, and Darren Strash. 2013. Listing All Maximal Cliques in Large Sparse Real-World Graphs. ACM Journal of Experimental Algorithmics 18 (2013)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/S004530010050"},{"key":"e_1_2_1_17_1","volume-title":"Fomin and Dieter Kratsch","author":"Fedor","year":"2010","unstructured":"Fedor V. Fomin and Dieter Kratsch. 2010. Exact Exponential Algorithms. Springer."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i9.21257"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2020.0984"},{"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":"Proc. WSDM'20","author":"Jain Shweta","unstructured":"Shweta Jain and C. Seshadhri. 2020. The Power of Pivoting for Exact Clique Counting. In Proc. WSDM'20. ACM, 268--276."},{"key":"e_1_2_1_22_1","volume-title":"Proc. of WWW'20","author":"Jain Shweta","year":"1966","unstructured":"Shweta Jain and C. Seshadhri. 2020. Provably and Efficiently Approximating Near-cliques using the Tur\u00e5n Shadow: PEANUTS. In Proc. of WWW'20. ACM \/ IW3C2, 1966--1976."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676847"},{"key":"e_1_2_1_24_1","volume-title":"Proc. of AAAI'24","author":"Jin Mingming","year":"2024","unstructured":"Mingming Jin, Jiongzhi Zheng, and Kun He. 2024. KD-Club: An Efficient Exact Algorithm with New Coloring-Based Upper Bound for the Maximum k-Defective Clique Problem. In Proc. of AAAI'24. 20735--20742."},{"key":"e_1_2_1_25_1","volume-title":"Aggarwal","author":"Lee Victor E.","year":"2010","unstructured":"Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu C. Aggarwal. 2010. A Survey of Algorithms for Dense Subgraph Discovery. In Managing and Mining Graph Data. Advances in Database Systems, Vol. 40. Springer, 303--336."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2013.143"},{"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":"publisher","DOI":"10.14778\/3407790.3407843"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_30_1","volume-title":"Foundations of Machine Learning","author":"Mohri Mehryar","unstructured":"Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. 2012. Foundations of Machine Learning. MIT Press."},{"key":"e_1_2_1_31_1","volume-title":"Pardalos and Jue Xue","author":"Panos","year":"1994","unstructured":"Panos M. Pardalos and Jue Xue. 1994. The maximum clique problem. J. global Optimization 4, 3 (1994), 301--328."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2014.986778"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.10.021"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90032-5"},{"key":"e_1_2_1_35_1","unstructured":"J. M. Robson. 2001. Finding a maximum independent set in time O(2n\/4). https:\/\/www.labri.fr\/perso\/robson\/mis\/techrep.html."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/14100018X"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1112\/jlms\/s1-38.1.423","article-title":"Regular Graphs with Given Girth and Restricted Circuits","volume":"1","author":"Sachs H.","year":"1963","unstructured":"H. Sachs. 1963. Regular Graphs with Given Girth and Restricted Circuits. Journal of the London Mathematical Society s1-38, 1 (1963), 423--429.","journal-title":"Journal of the London Mathematical Society s1-38"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.07.013"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.36.4.378.546"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01572-4"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Apichat Suratanee Martin H Schaefer Matthew J Betts Zita Soons Heiko Mannsperger Nathalie Harder Marcus Oswald Markus Gipp Ellen Ramminger Guillermo Marcus et al. 2014. Characterizing protein interactions employing a genome-wide siRNA cellular phenotyping screen. PLoS computational biology 10 9 (2014) e1003814.","DOI":"10.1371\/journal.pcbi.1003814"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206038"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-53925-6_1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11440-3_18"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-013-9548-5"},{"key":"e_1_2_1_47_1","volume-title":"Proc. of ICDE'13","author":"Xiang Jingen","year":"2013","unstructured":"Jingen Xiang, Cong Guo, and Ashraf Aboulnaga. 2013. Scalable maximum clique computation using mapreduce. In Proc. of ICDE'13. 74--85."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804355"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl014"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3705829.3705839","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:26:34Z","timestamp":1740785194000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3705829.3705839"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10.14778\/3705829.3705839"],"URL":"https:\/\/doi.org\/10.14778\/3705829.3705839","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"2025-02-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}