{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T03:33:58Z","timestamp":1778124838276,"version":"3.51.4"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:p>\n            Path-based solutions have been shown to be useful for various graph analysis tasks, such as link prediction and graph clustering. However, they are no longer adequate for handling complex and gigantic graphs. Recently,\n            <jats:italic>motif-based analysis<\/jats:italic>\n            has attracted a lot of attention. A motif, or a small graph with a few nodes, is often considered as a fundamental unit of a graph. Motif-based analysis captures high-order structure between nodes, and performs better than traditional \"edge-based\" solutions. In this paper, we study\n            <jats:italic>motif-path<\/jats:italic>\n            , which is conceptually a concatenation of one or more motif instances. We examine how motif-paths can be used in three path-based mining tasks, namely link prediction, local graph clustering and node ranking. We further address the situation when two graph nodes are not connected through a motif-path, and develop a novel defragmentation method to enhance it. Experimental results on real graph datasets demonstrate the use of motif-paths and defragmentation techniques improves graph analysis effectiveness.\n          <\/jats:p>","DOI":"10.14778\/3447689.3447714","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T16:20:06Z","timestamp":1618244406000},"page":"1111-1123","source":"Crossref","is-referenced-by-count":21,"title":["On analyzing graphs with motif-paths"],"prefix":"10.14778","volume":"14","author":[{"given":"Xiaodong","family":"Li","sequence":"first","affiliation":[{"name":"University of Hong Kong, Hong Kong SAR"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"University of Hong Kong, Hong Kong SAR"}]},{"given":"Kevin Chen-Chuan","family":"Chang","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}]},{"given":"Caihua","family":"Shan","sequence":"additional","affiliation":[{"name":"University of Hong Kong, Hong Kong SAR"}]},{"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"University of Hong Kong, Hong Kong SAR"}]},{"given":"Hongtai","family":"Cao","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}]}],"member":"320","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 412--429","author":"AbuOda Ghadeer","year":"2019","unstructured":"Ghadeer AbuOda , Gianmarco De Francisci Morales , and Ashraf Aboulnaga . 2019 . Link prediction via higher-order motif features . In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 412--429 . Ghadeer AbuOda, Gianmarco De Francisci Morales, and Ashraf Aboulnaga. 2019. Link prediction via higher-order motif features. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 412--429."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_2_1_3_1","volume-title":"Emergence of scaling in random networks. science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert . 1999. Emergence of scaling in random networks. science 286, 5439 ( 1999 ), 509--512. Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. science 286, 5439 (1999), 509--512."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.14"},{"key":"e_1_2_1_5_1","volume-title":"Higher-order organization of complex networks. Science 353, 6295","author":"Benson Austin R","year":"2016","unstructured":"Austin R Benson , David F Gleich , and Jure Leskovec . 2016. Higher-order organization of complex networks. Science 353, 6295 ( 2016 ), 163--166. Austin R Benson, David F Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science 353, 6295 (2016), 163--166."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_7_1","volume-title":"Research on the Influence of Network Motif on Link Prediction. DEStech Transactions on Computer Science and Engineering itms","author":"Cao Jie","year":"2016","unstructured":"Jie Cao , Bentian Li , and Xiangquan Gui . 2016. Research on the Influence of Network Motif on Link Prediction. DEStech Transactions on Computer Science and Engineering itms ( 2016 ). Jie Cao, Bentian Li, and Xiangquan Gui. 2016. Research on the Influence of Network Motif on Link Prediction. DEStech Transactions on Computer Science and Engineering itms (2016)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021940"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463722"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8257974"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055337"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2845414"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04532"},{"key":"e_1_2_1_14_1","volume-title":"Traffic Incident Detection: A Trajectory-based Approach. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE","author":"Han Xiaolin","year":"2020","unstructured":"Xiaolin Han , Tobias Grubenmann , Reynold Cheng , Sze Chun Wong , Xiaodong Li , and Wenya Sun . 2020 . Traffic Incident Detection: A Trajectory-based Approach. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE , 1866--1869. Xiaolin Han, Tobias Grubenmann, Reynold Cheng, Sze Chun Wong, Xiaodong Li, and Wenya Sun. 2020. Traffic Incident Detection: A Trajectory-based Approach. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 1866--1869."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt717"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1186\/1752-0509-2-73"},{"key":"e_1_2_1_19_1","unstructured":"Nevan J Krogan Gerard Cagney Haiyuan Yu Gouqing Zhong Xinghua Guo Alexandr Ignatchenko Joyce Li Shuye Pu Nira Datta Aaron P Tikuisis etal 2006. Global landscape of protein complexes in the yeast Saccharomyces cerevisiae. Nature (2006).  Nevan J Krogan Gerard Cagney Haiyuan Yu Gouqing Zhong Xinghua Guo Alexandr Ignatchenko Joyce Li Shuye Pu Nira Datta Aaron P Tikuisis et al. 2006. Global landscape of protein complexes in the yeast Saccharomyces cerevisiae. Nature (2006)."},{"key":"e_1_2_1_20_1","volume-title":"Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications 390, 6","author":"L\u00c3ij Linyuan","year":"2011","unstructured":"Linyuan L\u00c3ij and Tao Zhou . 2011. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications 390, 6 ( 2011 ), 1150 -- 1170. Linyuan L\u00c3ij and Tao Zhou. 2011. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications 390, 6 (2011), 1150 -- 1170."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330882"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2019.00-23"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447714"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447714"},{"key":"e_1_2_1_25_1","volume-title":"21st International Conference on Extending Database Technology (EDBT). 181--192","author":"Li Xiaodong","year":"2018","unstructured":"Xiaodong Li , Reynold Cheng , Yixiang Fang , Jiafeng Hu , and Silviu Maniu . 2018 . Scalable evaluation of k-nn queries on large uncertain graphs . In 21st International Conference on Extending Database Technology (EDBT). 181--192 . Xiaodong Li, Reynold Cheng, Yixiang Fang, Jiafeng Hu, and Silviu Maniu. 2018. Scalable evaluation of k-nn queries on large uncertain graphs. In 21st International Conference on Extending Database Technology (EDBT). 181--192."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3417440"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2898607.2898829"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2011.58"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.046122"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364330"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2981780.2981908"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx758"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-017-0544-8"},{"key":"e_1_2_1_34_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. 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_35_1","volume-title":"Neil A Goldenberg, Rebecca N Ichord, Janna M Journeycake, Ulrike Nowak-G\u00f6ttl, and Sara K Vesely.","author":"Monagle Paul","year":"2012","unstructured":"Paul Monagle , Anthony KC Chan , Neil A Goldenberg, Rebecca N Ichord, Janna M Journeycake, Ulrike Nowak-G\u00f6ttl, and Sara K Vesely. 2012 . Antithrombotic therapy in neonates and children: antithrombotic therapy and prevention of thrombosis: American College of Chest Physicians Evidence-Based Clinical Practice Guidelines . Chest (2012). Paul Monagle, Anthony KC Chan, Neil A Goldenberg, Rebecca N Ichord, Janna M Journeycake, Ulrike Nowak-G\u00f6ttl, and Sara K Vesely. 2012. Antithrombotic therapy in neonates and children: antithrombotic therapy and prevention of thrombosis: American College of Chest Physicians Evidence-Based Clinical Practice Guidelines. Chest (2012)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330995"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052597"},{"key":"e_1_2_1_38_1","volume-title":"Discrete mathematics and its applications: with combinatorics and graph theory","author":"Rosen Kenneth H","unstructured":"Kenneth H Rosen and Kamala Krithivasan . 2012. Discrete mathematics and its applications: with combinatorics and graph theory . Tata McGraw-Hill Education . Kenneth H Rosen and Kamala Krithivasan. 2012. Discrete mathematics and its applications: with combinatorics and graph theory. Tata McGraw-Hill Education."},{"key":"e_1_2_1_39_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 (2013), 2241. Ngoc Hieu Tran, Kwok Pui Choi, and Louxin Zhang. 2013. Counting motifs in the human interactome. Nature communications 4 (2013), 2241."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052653"},{"key":"e_1_2_1_41_1","volume-title":"SNOD: a fast sampling method of exploring node orbit degrees for large graphs. Knowledge and Information Systems","author":"Wang Pinghui","year":"2018","unstructured":"Pinghui Wang , Junzhou Zhao , Xiangliang Zhang , Jing Tao , and Xiaohong Guan . 2018. SNOD: a fast sampling method of exploring node orbit degrees for large graphs. Knowledge and Information Systems ( 2018 ), 1--26. Pinghui Wang, Junzhou Zhao, Xiangliang Zhang, Jing Tao, and Xiaohong Guan. 2018. SNOD: a fast sampling method of exploring node orbit degrees for large graphs. Knowledge and Information Systems (2018), 1--26."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_43_1","volume-title":"Link prediction in complex networks based on the interactions among paths. Physica A: Statistical Mechanics and its Applications 510","author":"Yao Yabing","year":"2018","unstructured":"Yabing Yao , Ruisheng Zhang , Fan Yang , Jianxin Tang , Yongna Yuan , and Rongjing Hu. 2018. Link prediction in complex networks based on the interactions among paths. Physica A: Statistical Mechanics and its Applications 510 ( 2018 ), 52--67. Yabing Yao, Ruisheng Zhang, Fan Yang, Jianxin Tang, Yongna Yuan, and Rongjing Hu. 2018. Link prediction in complex networks based on the interactions among paths. Physica A: Statistical Mechanics and its Applications 510 (2018), 52--67."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_2_1_45_1","volume-title":"Thirty-Second AAAI Conference on Artificial Intelligence.","author":"Zhao Huan","year":"2018","unstructured":"Huan Zhao , Xiaogang Xu , Yangqiu Song , Dik Lun Lee , Zhao Chen , and Han Gao . 2018 . Ranking users in social networks with higher-order structures . In Thirty-Second AAAI Conference on Artificial Intelligence. Huan Zhao, Xiaogang Xu, Yangqiu Song, Dik Lun Lee, Zhao Chen, and Han Gao. 2018. Ranking users in social networks with higher-order structures. In Thirty-Second AAAI Conference on Artificial Intelligence."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3447689.3447714","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:22:36Z","timestamp":1672226556000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3447689.3447714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["10.14778\/3447689.3447714"],"URL":"https:\/\/doi.org\/10.14778\/3447689.3447714","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,2]]}}}