{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:53:39Z","timestamp":1773482019804,"version":"3.50.1"},"reference-count":53,"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":"The Hong Kong Government and The Hong Kong Jockey Club Charities Trust"},{"name":"Research Grants Council, Hong Kong SAR","award":["16202722,15222118,15218919,15203120,15226221,15225921,15209922 and C2004-21GF"],"award-info":[{"award-number":["16202722,15222118,15218919,15203120,15226221,15225921,15209922 and C2004-21GF"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62072390,62102334"],"award-info":[{"award-number":["62072390,62102334"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>With an exponentially growing number of graphs from disparate repositories, there is a strong need to analyze a graph database containing an extensive collection of small- or medium-sized data graphs (e.g., chemical compounds). Although subgraph enumeration and subgraph mining have been proposed to bring insights into a graph database by a set of subgraph structures, they often end up with similar or homogenous topologies, which is undesirable in many graph applications. To address this limitation, we propose the Top-k Edge-Diversified Patterns Discovery problem to retrieve a set of subgraphs that cover the maximum number of edges in a database. To efficiently process such query, we present a generic and extensible framework called Ted which achieves a guaranteed approximation ratio to the optimal result. Two optimization strategies are further developed to improve the performance. Experimental studies on real-world datasets demonstrate the superiority of Ted to traditional techniques.<\/jats:p>","DOI":"10.1145\/3588736","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":5,"title":["TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3204-7949","authenticated-orcid":false,"given":"Kai","family":"Huang","sequence":"first","affiliation":[{"name":"Hong Kong Polytechnic University, The Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9008-2112","authenticated-orcid":false,"given":"Haibo","family":"Hu","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1547-2847","authenticated-orcid":false,"given":"Qingqing","family":"Ye","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-9578-8406","authenticated-orcid":false,"given":"Kai","family":"Tian","sequence":"additional","affiliation":[{"name":"Tencent, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8639-4570","authenticated-orcid":false,"given":"Bolong","family":"Zheng","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6343-1455","authenticated-orcid":false,"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, 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":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.10"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1758222.1758229"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.67"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45372-5_2"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.33"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.173"},{"key":"e_1_2_2_9_1","volume-title":"ICDM","author":"Yan X","year":"2002","unstructured":"Yan X, Han J W. gSpan: Graph-based Substructure pattern mining. In ICDM, 2002."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/951949.952101"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014134"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536263"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526761"},{"key":"e_1_2_2_15_1","volume-title":"Diversifying top-k results. PVLDB, 5(11)","author":"Qin L","year":"2012","unstructured":"Qin L, Yu J X, Chang L. Diversifying top-k results. PVLDB, 5(11), 2012."},{"key":"e_1_2_2_16_1","volume-title":"SIGMOD","author":"Huang K","year":"2019","unstructured":"Huang K, Chua H E, Bhowmick S S, et al. CATAPULT: data-driven selection of canned patterns for efficient visual graph query formulation. In SIGMOD, 2019."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554862"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384681"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137794"},{"key":"e_1_2_2_20_1","volume-title":"Exploratory search: Beyond the query-response paradigm. Synthesis lectures on information concepts, retrieval, and services, 1(1): 1--98","author":"White R W","year":"2009","unstructured":"White R W, Roth R A. Exploratory search: Beyond the query-response paradigm. Synthesis lectures on information concepts, retrieval, and services, 1(1): 1--98, 2009"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972795.60"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2034214.2034230"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746482"},{"key":"e_1_2_2_25_1","volume-title":"VLDB","author":"Toivonen H.","year":"1996","unstructured":"Toivonen H. Sampling large databases for association rules. In VLDB, 1996."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1841406"},{"key":"e_1_2_2_27_1","volume-title":"Instruments, & Computers, 35(3)","author":"Faulkner","year":"2003","unstructured":"Faulkner, Laura. Beyond the five-user assumption: Benefits of increased sample sizes in usability testing. Behavior Research Methods, Instruments, & Computers, 35(3), 2003."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544814"},{"key":"e_1_2_2_29_1","volume-title":"ICDM","author":"Al Hasan Mohammad","year":"2007","unstructured":"Al Hasan Mohammad, Chaoji Vineet, Salem Saeed, Besson Jeremy, Zaki Mohammed J. Origami: Mining representative orthogonal graph patterns. In ICDM, 2007."},{"key":"e_1_2_2_30_1","volume-title":"ICDM","author":"Zhang Shijie","year":"2009","unstructured":"Zhang Shijie, Yang Jiong, Li Shirong. Ring: An integrated method for frequent representative subgraph mining. In ICDM, 2009."},{"issue":"10","key":"e_1_2_2_31_1","first-page":"974","article-title":"Scalable subgraph enumeration in mapreduce","volume":"8","author":"Lai L","year":"2015","unstructured":"Lai L, Qin L, Lin X, et al. Scalable subgraph enumeration in mapreduce. VLDBJ, 8(10): 974--985, 2015.","journal-title":"VLDBJ"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588557"},{"key":"e_1_2_2_33_1","volume-title":"SIGMOD","author":"Kim H","year":"2016","unstructured":"Kim H, Lee J, Bhowmick S S, et al. Dualsim: Parallel subgraph enumeration in a massive graph on a single machine. In SIGMOD, 2016."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00029"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149198"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113337"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18120-2_18"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389699"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839491"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956784"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376662"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.133"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989405"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487689"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113300"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.49"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00706-0"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457251"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407846"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007299"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915216"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939848"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00604-x"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588736","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588736","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:36Z","timestamp":1750178856000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588736"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588736"],"URL":"https:\/\/doi.org\/10.1145\/3588736","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}