{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T16:12:26Z","timestamp":1786637546648,"version":"3.56.0"},"reference-count":93,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>In the heterogeneous information network (HIN), a motif-clique is a \"complete graph\" for a given motif (or a small connected graph) that could capture the desired relationship in the motif. The maximal motif-cliques of HINs have found various applications in community discovery, recommendation, and biological network analysis. The state-of-the-art algorithm for enumerating maximal motif-cliques may have to explore all possible subgraphs of a maximal motif-clique and check whether a maximal motif-clique has been enumerated at each recursive step, which is very time-consuming. To improve the efficiency of enumeration, in this paper, we develop efficient algorithms for maximal motif-clique enumeration over large HINs. We first introduce an order-based framework to avoid duplicated enumeration, which results in lower time complexity compared to the existing algorithm. We then propose a pivot-based pruning strategy, which significantly reduces the search space. We further optimize the process of identifying the candidate sets and locating the subgraphs containing the maximal motif-cliques. Extensive experiments on five real-world HINs demonstrate that our proposed algorithm achieves high efficiency and is up to three orders of magnitude faster than the state-of-the-art algorithm.<\/jats:p>","DOI":"10.14778\/3681954.3681975","type":"journal-article","created":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T16:23:36Z","timestamp":1725035016000},"page":"2946-2959","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks"],"prefix":"10.14778","volume":"17","author":[{"given":"Yingli","family":"Zhou","sequence":"first","affiliation":[{"name":"The Chinese University of Hong, Kong, Shenzhen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong, Kong, Shenzhen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong, Kong, Shenzhen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tianci","family":"Hou","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong, Kong, Shenzhen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,8,30]]},"reference":[{"key":"e_1_2_1_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_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"e_1_2_1_3_1","volume-title":"An o (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049","author":"Batagelj Vladimir","year":"2003","unstructured":"Vladimir Batagelj and Matjaz Zaversnik. 2003. An o (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 (2003)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1102022211"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0561-2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557039"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_1_8_1","volume-title":"Statistical analysis of financial networks. Computational statistics & data analysis 48, 2","author":"Boginski Vladimir","year":"2005","unstructured":"Vladimir Boginski, Sergiy Butenko, and Panos M Pardalos. 2005. Statistical analysis of financial networks. Computational statistics & data analysis 48, 2 (2005), 431--443."},{"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.1145\/3077136.3080779"},{"key":"e_1_2_1_11_1","volume-title":"Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3","author":"Carletti Vincenzo","year":"2017","unstructured":"Vincenzo Carletti, Pasquale Foggia, Alessia Saggese, and Mario Vento. 2017. Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3. IEEE transactions on pattern analysis and machine intelligence 40, 4 (2017), 804--818."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401198"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330986"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9632-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3564284","article-title":"Bias and debias in recommender system: A survey and future directions","volume":"41","author":"Chen Jiawei","year":"2023","unstructured":"Jiawei Chen, Hande Dong, Xiang Wang, Fuli Feng, Meng Wang, and Xiangnan He. 2023. Bias and debias in recommender system: A survey and future directions. ACM Transactions on Information Systems 41, 3 (2023), 1--39.","journal-title":"ACM Transactions on Information Systems"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3459241"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529341"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Liang Chen Yang Liu Xiangnan He Lianli Gao and Zibin Zheng. 2019. Matching user with item set: Collaborative bundle recommendation with deep attention network.. In IJCAI. 2095--2101.","DOI":"10.24963\/ijcai.2019\/290"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021940"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380119"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043652.2043654"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339724"},{"key":"e_1_2_1_23_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming (ICALP","author":"Conte Alessio","year":"2016","unstructured":"Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari. 2016. Sublinearspace bounded-delay enumeration for massive network analytics: Maximal cliques. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526143"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557444"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2018.00016"},{"key":"e_1_2_1_28_1","volume-title":"Arboricity and bipartite subgraph listing algorithms. Information processing letters 51, 4","author":"Eppstein David","year":"1994","unstructured":"David Eppstein. 1994. Arboricity and bipartite subgraph listing algorithms. Information processing letters 51, 4 (1994), 207--211."},{"key":"e_1_2_1_29_1","first-page":"3","article-title":"Listing all maximal cliques in large sparse real-world graphs","volume":"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. Journal of Experimental Algorithmics (JEA) 18 (2013), 3--1.","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884455"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.166"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737791"},{"key":"e_1_2_1_35_1","volume-title":"Frequent pattern mining: current status and future directions. Data mining and knowledge discovery 15, 1","author":"Han Jiawei","year":"2007","unstructured":"Jiawei Han, Hong Cheng, Dong Xin, and Xifeng Yan. 2007. Frequent pattern mining: current status and future directions. Data mining and knowledge discovery 15, 1 (2007), 55--86."},{"key":"e_1_2_1_36_1","unstructured":"Jiawei Han Jian Pei and Hanghang Tong. 2022. Data mining: concepts and techniques. Morgan kaufmann."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052569"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00072"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/3535850.3535925"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401969"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0507841103"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90065-8"},{"key":"e_1_2_1_45_1","volume-title":"Learning to discover social circles in ego networks. Advances in neural information processing systems 25","author":"Leskovec Jure","year":"2012","unstructured":"Jure Leskovec and Julian Mcauley. 2012. Learning to discover social circles in ego networks. Advances in neural information processing systems 25 (2012)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00154"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190660"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407843"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00031"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00108"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447714"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1970-125-1"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22146"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings 9. Springer, 260--272","author":"Makino Kazuhisa","year":"2004","unstructured":"Kazuhisa Makino and Takeaki Uno. 2004. New algorithms for enumerating all maximal cliques. In Algorithm Theory-SWAT 2004: 9th Scandinavian Workshop on Algorithm Theory, Humleb\u00e6k, Denmark, July 8--10, 2004. Proceedings 9. Springer, 260--272."},{"key":"e_1_2_1_56_1","volume-title":"Network motifs: simple building blocks of complex networks. Science 298, 5594","author":"Milo Ron","year":"2002","unstructured":"Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: simple building blocks of complex networks. Science 298, 5594 (2002), 824--827."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314183.3324976"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.016"},{"key":"e_1_2_1_59_1","volume-title":"Uncovering the overlapping community structure of complex networks in nature and society. nature 435, 7043","author":"Palla Gergely","year":"2005","unstructured":"Gergely Palla, Imre Der\u00e9nyi, Ill\u00e9s Farkas, and Tam\u00e1s Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. nature 435, 7043 (2005), 814--818."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.3390\/a12010023"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052597"},{"key":"e_1_2_1_62_1","volume-title":"Network analytics in the age of big data. Science 353, 6295","author":"Pr\u017eulj Nata\u0161a","year":"2016","unstructured":"Nata\u0161a Pr\u017eulj and No\u00ebl Malod-Dognin. 2016. Network analytics in the age of big data. Science 353, 6295 (2016), 123--124."},{"key":"e_1_2_1_63_1","volume-title":"Discrete mathematics and its applications","author":"Rosen Kenneth H","unstructured":"Kenneth H Rosen. 2007. Discrete mathematics and its applications. The McGraw Hill Companies,."},{"key":"e_1_2_1_64_1","volume-title":"International Workshop on Theory and Application of Graph Transformations. Springer, 238--251","author":"Rudolf Michael","year":"1998","unstructured":"Michael Rudolf. 1998. Utilizing constraint satisfaction techniques for efficient graph pattern matching. In International Workshop on Theory and Application of Graph Transformations. Springer, 238--251."},{"key":"e_1_2_1_65_1","volume-title":"Obtaining maximal concatenated phylogenetic data sets from large sequence databases. Molecular biology and evolution 20, 7","author":"Sanderson Michael J","year":"2003","unstructured":"Michael J Sanderson, Amy C Driskell, Richard H Ree, Oliver Eulenstein, and Sasha Langley. 2003. Obtaining maximal concatenated phylogenetic data sets from large sequence databases. Molecular biology and evolution 20, 7 (2003), 1036--1042."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.01.003"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974348.36"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447846"},{"key":"e_1_2_1_70_1","doi-asserted-by":"crossref","unstructured":"Chuan Shi Xiangnan Kong Philip S Yu Sihong Xie and Bin Wu. 2012. Relevance search in heterogeneous networks. In EDBT. 180--191.","DOI":"10.1145\/2247596.2247618"},{"key":"e_1_2_1_71_1","doi-asserted-by":"crossref","unstructured":"Chuan Shi Chong Zhou Xiangnan Kong Philip S Yu Gang Liu and Bai Wang. 2012. Heterecom: a semantic-based recommendation system in heterogeneous networks. In KDD. 1552--1555.","DOI":"10.1145\/2339530.2339778"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402736"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206038"},{"key":"e_1_2_1_75_1","volume-title":"The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science 363, 1","author":"Tomita Etsuji","year":"2006","unstructured":"Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. 2006. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science 363, 1 (2006), 28--42."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350277"},{"key":"e_1_2_1_77_1","volume-title":"Kwok Pui Choi, and Louxin Zhang","author":"Tran Ngoc Hieu","year":"2013","unstructured":"Ngoc Hieu Tran, Kwok Pui Choi, and Louxin Zhang. 2013. Counting motifs in the human interactome. Nature communications 4, 1 (2013), 2241."},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.030"},{"key":"e_1_2_1_79_1","volume-title":"Bias in Knowledge Graphs-an Empirical Study with Movie Recommendation and Different Language Editions of DBpedia. arXiv preprint arXiv:2105.00674","author":"Voit Michael Matthias","year":"2021","unstructured":"Michael Matthias Voit and Heiko Paulheim. 2021. Bias in Knowledge Graphs-an Empirical Study with Movie Recommendation and Different Language Editions of DBpedia. arXiv preprint arXiv:2105.00674 (2021)."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2023.126608"},{"key":"e_1_2_1_81_1","volume-title":"Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks. PVLDB","author":"Wang Kai","year":"2019","unstructured":"Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2019. Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks. PVLDB (2019)."},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77018-3_47"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3494523"},{"key":"e_1_2_1_84_1","volume-title":"Evolutionary conservation of motif constituents in the yeast protein interaction network. Nature genetics 35, 2","author":"Wuchty Stephan","year":"2003","unstructured":"Stephan Wuchty, Zolt\u00e1n N Oltvai, and Albert-L\u00e1szl\u00f3 Barab\u00e1si. 2003. Evolutionary conservation of motif constituents in the yeast protein interaction network. Nature genetics 35, 2 (2003), 176--179."},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.06.001"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.Congress.2014.31"},{"key":"e_1_2_1_87_1","volume-title":"q)-biclique counting and enumeration for large sparse bipartite graphs. The VLDB Journal","author":"Yang Jianye","year":"2023","unstructured":"Jianye Yang, Yun Peng, Dian Ouyang, Wenjie Zhang, Xuemin Lin, and Xiang Zhao. 2023. (p, q)-biclique counting and enumeration for large sparse bipartite graphs. The VLDB Journal (2023), 1--25."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00083"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_2_1_90_1","unstructured":"Chenhao Ma Tianci Hou Xin Huang Yingli Zhou Yixiang Fang. 2023. Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks (technical report). https:\/\/github.com\/EnderturtleOrz\/VLDB2024-Mclique\/blob\/master\/VLDB2024-Mclique-Technique-Report.pdf."},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556233"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/2507157.2507230"},{"key":"e_1_2_1_93_1","volume-title":"On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types. BMC bioinformatics 15","author":"Zhang Yun","year":"2014","unstructured":"Yun Zhang, Charles A Phillips, Gary L Rogers, Erich J Baker, Elissa J Chesler, and Michael A Langston. 2014. On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types. BMC bioinformatics 15 (2014), 1--18."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3681954.3681975","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:47:03Z","timestamp":1725475623000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3681954.3681975"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":93,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.14778\/3681954.3681975"],"URL":"https:\/\/doi.org\/10.14778\/3681954.3681975","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"2024-08-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}