{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T03:01:41Z","timestamp":1775617301189,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p>\n            Given a user-specified minimum degree threshold\n            <jats:italic>\u03b3<\/jats:italic>\n            , a\n            <jats:italic>\u03b3<\/jats:italic>\n            -quasiclique is a subgraph\n            <jats:italic>g<\/jats:italic>\n            <jats:bold>=<\/jats:bold>\n            <jats:italic>\n              (V\n              <jats:sub>g<\/jats:sub>\n              , E\n              <jats:sub>g<\/jats:sub>\n              )\n            <\/jats:italic>\n            where each vertex\n            <jats:italic>\n              \u03bd \u2208 V\n              <jats:sub>g<\/jats:sub>\n            <\/jats:italic>\n            connects to at least\n            <jats:italic>\u03b3<\/jats:italic>\n            fraction of the other vertices (i.e., \u2308\n            <jats:italic>\u03b3<\/jats:italic>\n            \u00b7 (|\n            <jats:italic>\n              V\n              <jats:sub>g<\/jats:sub>\n            <\/jats:italic>\n            |- 1)\u2309 vertices) in\n            <jats:italic>g.<\/jats:italic>\n            Quasi-clique is one of the most natural definitions for dense structures useful in finding communities in social networks and discovering significant biomolecule structures and pathways. However, mining maximal quasi-cliques is notoriously expensive.\n          <\/jats:p>\n          <jats:p>In this paper, we design parallel algorithms for mining maximal quasi-cliques on G-thinker, a distributed graph mining framework that decomposes mining into compute-intensive tasks to fully utilize CPU cores. We found that directly using G-thinker results in the straggler problem due to (i) the drastic load imbalance among different tasks and (ii) the difficulty of predicting the task running time. We address these challenges by redesigning G-thinker's execution engine to prioritize long-running tasks for execution, and by utilizing a novel timeout strategy to effectively decompose long-running tasks to improve load balancing. While this system redesign applies to many other expensive dense subgraph mining problems, this paper verifies the idea by adapting the state-of-the-art quasi-clique algorithm, Quick, to our redesigned G-thinker. Extensive experiments verify that our new solution scales well with the number of CPU cores, achieving 201\u00d7 runtime speedup when mining a graph with 3.77M vertices and 16.5M edges in a 16-node cluster.<\/jats:p>","DOI":"10.14778\/3436905.3436916","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T17:23:50Z","timestamp":1614014630000},"page":"573-585","source":"Crossref","is-referenced-by-count":27,"title":["Scalable mining of maximal quasi-cliques"],"prefix":"10.14778","volume":"14","author":[{"given":"Guimu","family":"Guo","sequence":"first","affiliation":[{"name":"University of Alabama at Birmingham"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Da","family":"Yan","sequence":"additional","affiliation":[{"name":"University of Alabama at Birmingham"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. Tamer","family":"\u00d6zsu","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhe","family":"Jiang","sequence":"additional","affiliation":[{"name":"University of Alabama"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jalal","family":"Khalil","sequence":"additional","affiliation":[{"name":"University of Alabama at Birmingham"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Code of the BigData 2018 Paper on Large Quasi-Clique Mining. https:\/\/github.com\/beginner1010\/topk-quasi-clique-enumeration.  [n.d.]. Code of the BigData 2018 Paper on Large Quasi-Clique Mining. https:\/\/github.com\/beginner1010\/topk-quasi-clique-enumeration."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. COST in the Land of Databases. https:\/\/github.com\/frankmcsherry\/blog\/blob\/master\/posts\/2017-09-23.md.  [n.d.]. COST in the Land of Databases. https:\/\/github.com\/frankmcsherry\/blog\/blob\/master\/posts\/2017-09-23.md."},{"key":"e_1_2_1_3_1","unstructured":"[n.d.]. Our code. https:\/\/github.com\/yanlab19870714\/gthinkerQC.  [n.d.]. Our code. https:\/\/github.com\/yanlab19870714\/gthinkerQC."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/646389.690506"},{"key":"e_1_2_1_5_1","volume-title":"An automated method for finding molecular complexes in large protein interaction networks. BMC bioinformatics 4, 1","author":"Bader Gary D","year":"2003"},{"key":"e_1_2_1_6_1","volume-title":"CoRR cs.DS\/0310049","author":"Batagelj Vladimir","year":"2003"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746478"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICAIS.2009.39"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92695-5_4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Dongbo Bu Yi Zhao Lun Cai Hong Xue Xiaopeng Zhu Hongchao Lu Jingfen Zhang Shiwei Sun Lunjiang Ling Nan Zhang etal 2003. Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic acids research 31 9 (2003) 2443--2450.  Dongbo Bu Yi Zhao Lun Cai Hong Xue Xiaopeng Zhu Hongchao Lu Jingfen Zhang Shiwei Sun Lunjiang Ling Nan Zhang et al. 2003. Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic acids research 31 9 (2003) 2443--2450.","DOI":"10.1093\/nar\/gkg340"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465323"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5220\/0005498400050015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382577.2382581"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-018-0497-y"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098031"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220093"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463722"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389745"},{"key":"e_1_2_1_19_1","volume-title":"Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach. CoRR abs\/2005.00081","author":"Guo Guimu","year":"2020"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0307750100"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti1049"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1460797.1460799"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276313"},{"key":"e_1_2_1_24_1","volume-title":"Lakshmanan","author":"Lee Pei","year":"2016"},{"key":"e_1_2_1_25_1","volume-title":"Uncovering the overlapping community structure of complex networks by maximal cliques. Physica A: Statistical Mechanics and its Applications 415","author":"Li Junqiu","year":"2014"},{"key":"e_1_2_1_26_1","volume-title":"ECML\/PKDD (Lecture Notes in Computer Science)","author":"Liu Guimei"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137660"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00091-7"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.07.019"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081898"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","volume-title":"Enumerating Top-k Quasi-Cliques","author":"Sanei-Mehri Seyed-Vahid","DOI":"10.1109\/BigData.2018.8622352"},{"key":"e_1_2_1_33_1","volume-title":"6th Conference on Email and Anti-Spam (CEAS)","author":"Sheng Steve","year":"2009"},{"key":"e_1_2_1_34_1","volume-title":"Koobface: The evolution of the social botnet. In eCrime","author":"Tanner Brian K.","year":"2010"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11871637_36"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1363686.1364019"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of Annual ADFSL Conference on Digital Forensics, Security and Law.","author":"Weiss Daniel","year":"2015"},{"key":"e_1_2_1_38_1","volume-title":"Tamer \u00d6zsu, Wei-Shinn Ku, and John C.S. Lui.","author":"Yan Da","year":"2020"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150506"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3436905.3436916","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:25:46Z","timestamp":1672223146000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3436905.3436916"}},"subtitle":["an algorithm-system codesign approach"],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.14778\/3436905.3436916"],"URL":"https:\/\/doi.org\/10.14778\/3436905.3436916","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}