{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:20:35Z","timestamp":1753881635845,"version":"3.41.2"},"reference-count":42,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T00:00:00Z","timestamp":1624924800000},"content-version":"vor","delay-in-days":179,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61472169","61502215","62072220","U1811261"],"award-info":[{"award-number":["61472169","61502215","62072220","U1811261"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"publisher","award":["2020M672134"],"award-info":[{"award-number":["2020M672134"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007620","name":"Department of Education of Liaoning Province","doi-asserted-by":"publisher","award":["LJC201913"],"award-info":[{"award-number":["LJC201913"]}],"id":[{"id":"10.13039\/501100007620","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Complexity"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Interesting subgraph query aims to find subgraphs that are isomorphic to the given query graph from a data graph and rank the subgraphs according to their interestingness scores. However, the existing subgraph query approaches are inefficient when dealing with large\u2010scale labeled data graph. This is caused by the following problems: (i) the existing work mainly focuses on unweighted query graphs, while ignoring the impact of query constraints on query results. (ii) Excessive number of subgraph candidates or complex joins between nodes in the subgraph candidates reduce the query efficiency. To solve these problems, this paper proposes an intelligent solution. Firstly, an Isotype Structure Graph Compression (ISGC) strategy is proposed to compress similar nodes in a graph to reduce the size of the graph and avoid unnecessary matching. Then, an auxiliary data structure Supergraph Topology Feature Index (STFIndex) is designed to replace the storage of the original data graph and improve the efficiency of an online query. After that, a partition method based on Edge Label Step Value (ELSV) is proposed to partition the index logically. In addition, a novel Top\u2010K interest subgraph query approach is proposed, which consists of the multidimensional filtering (MDF) strategy, upper bound value (UBV) (Size\u2010c) matching, and the optimizational join (QJ) method to filter out as many false subgraph candidates as possible to achieve fast joins. We conduct experiments on real and synthetic datasets. Experimental results show that the average performance of our approach is 1.35 higher than that of the state\u2010of\u2010the\u2010art approaches when the query graph is unweighted, and the average performance of our approach is 2.88 higher than that of the state\u2010of\u2010the\u2010art approaches when the query graph is weighted.<\/jats:p>","DOI":"10.1155\/2021\/9274429","type":"journal-article","created":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:20:21Z","timestamp":1625008821000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Supergraph Topology Feature Index for Personalized Interesting Subgraph Query in Large Labeled Graphs"],"prefix":"10.1155","volume":"2021","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1356-1304","authenticated-orcid":false,"given":"Xiaohuan","family":"Shan","sequence":"first","affiliation":[]},{"given":"Haihai","family":"Li","sequence":"additional","affiliation":[]},{"given":"Chunjie","family":"Jia","sequence":"additional","affiliation":[]},{"given":"Dong","family":"Li","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4285-578X","authenticated-orcid":false,"given":"Baoyan","family":"Song","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2021,6,29]]},"reference":[{"key":"e_1_2_10_1_2","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-017-1525-z"},{"key":"e_1_2_10_2_2","unstructured":"BingxianL. ZhichengZ. LeiW.et al. Confining Wi-Fi coverage: a crowdsourced method using physical layer information Proceedings of the 13th Annual IEEE International Conference on Sensing Communication and Networking (SECON) June 2016 London UK 1\u20139."},{"key":"e_1_2_10_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11036-018-1088-x"},{"key":"e_1_2_10_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/tnnls.2016.2515080"},{"key":"e_1_2_10_5_2","unstructured":"Tencent Technology WeChat\u2019s monthly active users had 1.12 billion increased year-one-year by 6.9% 2020 https:\/\/tech.qq.com\/a\/20190515\/007600.htm."},{"key":"e_1_2_10_6_2","unstructured":"Tencent Technology Facebook\u2019s monthly active users had 2.45 billion income increased year-one-year by 30% in the third quarter 2020 https:\/\/tech.qq.com\/a\/20191031\/001015.htm."},{"key":"e_1_2_10_7_2","unstructured":"AbdelhamidE. AbdelazizI. KhayyatZ. andKalnisP. Pivoted subgraph isomorphism: the optimist the pessimist and the realist Proceedings of the 22nd International Conference on Extending Database Technology EDBT 2019 March 2019 Lisbon Portugal 361\u2013372."},{"key":"e_1_2_10_8_2","doi-asserted-by":"publisher","DOI":"10.13328\/j.cnki.jos.005696"},{"key":"e_1_2_10_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/tbdata.2016.2625307"},{"key":"e_1_2_10_10_2","doi-asserted-by":"crossref","unstructured":"AbulaishM. AnsariZ. A. andJahiruddinS. SubISO: a scalable and novel approach for subgraph isomorphism search in large graph Proceedings of the 11th International Conference on Communication Systems and Networks (COMSNETS) January 2019 Bangalore India 1\u20138.","DOI":"10.1109\/COMSNETS.2019.8711459"},{"key":"e_1_2_10_11_2","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339494"},{"key":"e_1_2_10_12_2","doi-asserted-by":"crossref","unstructured":"KimJ. ShinH. HanW.-S. HongS. andChafiH. Taming subgraph isomorphism for RDF query processing Proceedings of the VLDB Endowment February 2015 Kohala Coast HI USA 1238\u20131249.","DOI":"10.14778\/2809974.2809985"},{"key":"e_1_2_10_13_2","doi-asserted-by":"crossref","unstructured":"GuptaM. GaoJ. YanX. CamH. andHanJ. Top-K interesting subgraph discovery in information networks Proceedings of the IEEE 30th International Conference on Data Engineering ICDE March 2014 Chicago IL USA 820\u2013831 https:\/\/doi.org\/10.1109\/icde.2014.6816703 2-s2.0-84901754968.","DOI":"10.1109\/ICDE.2014.6816703"},{"key":"e_1_2_10_14_2","doi-asserted-by":"publisher","DOI":"10.3390\/info10020061"},{"key":"e_1_2_10_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1979","author":"Garey M. R.","key":"e_1_2_10_16_2"},{"key":"e_1_2_10_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/tpami.2004.75"},{"key":"e_1_2_10_18_2","unstructured":"HolderL. B. CookD. andDjokoS. Substructure discovery in the SUBDUE system Proceedings of the Workshop on Knowledge Discovery in Databases KDD\u201994 July 1994 Seattle WA USA 169\u2013180."},{"key":"e_1_2_10_19_2","doi-asserted-by":"crossref","unstructured":"ZhuF. QuQ. LoD. YanX. HanJ. andYuP. S. Mining top-K large structural patterns in a massive network Proceedings of the 37th International Conference on Very Large Data Bases VLDB\u201911 August 2011 Seattle WA USA 807\u2013818.","DOI":"10.14778\/3402707.3402720"},{"key":"e_1_2_10_20_2","doi-asserted-by":"publisher","DOI":"10.3233\/ida-173705"},{"key":"e_1_2_10_21_2","doi-asserted-by":"crossref","unstructured":"HeH.andSinghA. K. Query language and access methods for graph databases Proceedings of the 2008 ACM SIGMOD international conference on Management of data SIGMOD 2008 June 2008 Vancouver Canada 405\u2013418 https:\/\/doi.org\/10.1007\/978-1-4419-6045-0_4.","DOI":"10.1007\/978-1-4419-6045-0_4"},{"key":"e_1_2_10_22_2","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"},{"key":"e_1_2_10_23_2","doi-asserted-by":"crossref","unstructured":"BiF. ChangL. LinX.et al. Efficient subgraph matching by postponing Cartesian products Proceedings of the 2016 International Conference on Management of Data SIGMOD \u201916 June 2016 San Francisco CA USA 1199\u20131214 https:\/\/doi.org\/10.1145\/2882903.2915236 2-s2.0-84979715993.","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_10_24_2","doi-asserted-by":"crossref","unstructured":"BhattaraiB. LiuH. andHowie HuangH. CECI: compact embedding cluster index for scalable subgraph matching Proceedings of the 2019 International Conference on Management of Data SIGMOD\u201919 June 2019 Amsterdam Netherlands 1447\u20131462 https:\/\/doi.org\/10.1145\/3299869.3300086 2-s2.0-85069220330.","DOI":"10.1145\/3299869.3300086"},{"key":"e_1_2_10_25_2","doi-asserted-by":"crossref","unstructured":"HeH.andSinghA. K. Filtering strategies for inexact subgraph matching on noisy multiplex networks Proceedings of the 2019 IEEE International Conference on Big Data December 2019 Los Angeles CA USA 4906\u20134912 https:\/\/doi.org\/10.1109\/BigData47090.2019.9006047.","DOI":"10.1109\/BigData47090.2019.9006047"},{"key":"e_1_2_10_26_2","doi-asserted-by":"crossref","unstructured":"HanM. KimH. GuG.et al. Efficient subgraph matching: harmonizing dynamic programming adaptive matching order and failing set together Proceedings of the 2019 ACM SIGMOD International Conference on Management of Data SIGMOD \u201919 June 2019 Amsterdam Netherlands 1429\u20131446 https:\/\/doi.org\/10.1145\/3299869.3319880 2-s2.0-85069531305.","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_10_27_2","doi-asserted-by":"crossref","unstructured":"ParkY. KoS. BhowmickS. S.et al. G-CARE: a framework for performance benchmarking of cardinality estimation techniques for subgraph matching Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data SIGMOD \u201920 June 2020 Portland OR USA 1099\u20131114 https:\/\/doi.org\/10.1145\/3318464.3389702.","DOI":"10.1145\/3318464.3389702"},{"key":"e_1_2_10_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.12.010"},{"key":"e_1_2_10_29_2","unstructured":"HanW. S. LeeJ. andLeeJ. H. TurboISO: towards ultrafast and robust subgraph isomorphism search in large graph databases Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data SIGMOD\u201913 June 2013 New York NY USA 337\u2013348."},{"key":"e_1_2_10_30_2","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735493"},{"key":"e_1_2_10_31_2","doi-asserted-by":"publisher","DOI":"10.11897\/SP.J.1016.2017.00052"},{"key":"e_1_2_10_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2017.04.005"},{"key":"e_1_2_10_33_2","doi-asserted-by":"crossref","unstructured":"YanX. HeB. ZhuF. andHanJ. Top-K aggregation queries over large networks Proceedings of the 26th International Conference on Data Engineering ICDE 2010 March 2010 Long Beach CA USA 377\u2013380 https:\/\/doi.org\/10.1109\/icde.2010.5447863 2-s2.0-77952765716.","DOI":"10.1109\/ICDE.2010.5447863"},{"key":"e_1_2_10_34_2","doi-asserted-by":"crossref","unstructured":"YangS. HanF. WuY. andYanX. Fast top-K search in knowledge graphs Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering ICDE\u201916 May 2016 Helsinki Finland https:\/\/doi.org\/10.1109\/icde.2016.7498307 2-s2.0-84980370962.","DOI":"10.1109\/ICDE.2016.7498307"},{"key":"e_1_2_10_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/access.2018.2819426"},{"key":"e_1_2_10_36_2","doi-asserted-by":"crossref","unstructured":"YangZ. FuA. W. andLiuR. Diversified top-K subgraph querying in a large graph Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data SIGMOD\u201916 June 2016 San Francisco CA USA 1167\u20131182 https:\/\/doi.org\/10.1145\/2882903.2915216 2-s2.0-84979713564.","DOI":"10.1145\/2882903.2915216"},{"key":"e_1_2_10_37_2","doi-asserted-by":"crossref","unstructured":"Fournier-VigerP. ChengC. LinJ. C.-W. YunU. andKiranR. U. TKG: efficient mining of top-K frequent subgraphs Proceedings of the 7th International Conference on Big Data Analytics BDA 2019 December 2019 Ahmedabad India 209\u2013226 https:\/\/doi.org\/10.1007\/978-3-030-37188-3_13.","DOI":"10.1007\/978-3-030-37188-3_13"},{"key":"e_1_2_10_38_2","doi-asserted-by":"publisher","DOI":"10.1142\/s0218001418500209"},{"key":"e_1_2_10_39_2","doi-asserted-by":"crossref","unstructured":"AminN. KhanK. U. DolgorsurenB. andLeeY. K. Extracting top-K interesting subgraphs with weighted query semantics Proceedings of the IEEE International Conference on Big Data and Smart Computing BigComp February 2017 Jeju Island South Korea 366\u2013373 https:\/\/doi.org\/10.1109\/bigcomp.2017.7881695 2-s2.0-85017591081.","DOI":"10.1109\/BIGCOMP.2017.7881695"},{"key":"e_1_2_10_40_2","unstructured":"BendimeradA. MelA. LijffijtJ. PlantevitM. RobardetC. andBieT. D. Mining subjectively interesting attributed subgraphs Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG) May 2018 London UK."},{"key":"e_1_2_10_41_2","doi-asserted-by":"publisher","DOI":"10.1142\/s0218488519500132"},{"key":"e_1_2_10_42_2","doi-asserted-by":"crossref","unstructured":"ChakrabartiD. ZhanY. andFaloutsosC. R-MAT: a recursive model for graph mining Proceedings of the Siam International Conference on Data Mining SDM\u201904 April 2004 Lake Buena Vista FL USA 442\u2013446 https:\/\/doi.org\/10.1137\/1.9781611972740.43.","DOI":"10.1137\/1.9781611972740.43"}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2021\/9274429.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2021\/9274429.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2021\/9274429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T22:20:18Z","timestamp":1723242018000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2021\/9274429"}},"subtitle":[],"editor":[{"given":"chuan","family":"lin","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1155\/2021\/9274429"],"URL":"https:\/\/doi.org\/10.1155\/2021\/9274429","archive":["Portico"],"relation":{},"ISSN":["1076-2787","1099-0526"],"issn-type":[{"type":"print","value":"1076-2787"},{"type":"electronic","value":"1099-0526"}],"subject":[],"published":{"date-parts":[[2021,1]]},"assertion":[{"value":"2021-04-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-04","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"9274429"}}