{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:46:33Z","timestamp":1740181593377,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T00:00:00Z","timestamp":1719964800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T00:00:00Z","timestamp":1719964800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Johann Wolfgang Goethe-Universit\u00e4t, Frankfurt am Main"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The subgraph searching is a fundamental operation for the analysis and exploration of graphs. Nowadays, molecular databases are nearing close to one hundred million molecules. Since finding all the data graphs in a graph database that contain the query graph using subgraph isomorphism is an NP-complete problem, indexes are built and processed. Further, to assist the formulation of the query by a user, the visual exploratory subgraph query paradigm proposes a graphical user interface and leverages exploration time to reduce query processing time. However, state-of-the-art approaches need to scale better to dynamic graph databases and suffer from efficiency problems. In addition, the existing <jats:bold>Sum<\/jats:bold>marisation-based frequent subgraph mining for visual <jats:bold>exploratory<\/jats:bold> subgraph searching (SuMExplorer) is lacking implementation and evaluation study for handling visual subgraph similarity search and modify operations. In this paper, we present a novel index structure, which aids the subgraph searching using the summarised-based weighted frequent subgraph mining on data graphs. By the structure-preserving, we exploit the indexes to support similarity and modify operations. We conduct extensive performance studies on both real-world and synthetic datasets to evaluate the overall performance of the extended SuMExplorer to the recent visual exploratory FERRARI and traditional subgraph search algorithms (such as the gIndex and the GRAPES-DD). Our results showed that our indexes can query up to 3 times faster in comparison to the FERRARI while reducing the storage footprint by 2 orders of magnitude.<\/jats:p>","DOI":"10.1007\/s42979-024-03006-w","type":"journal-article","created":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T07:03:01Z","timestamp":1719990181000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An Experimental Evaluation of Summarisation-Based Frequent Subgraph Mining for Subgraph Searching"],"prefix":"10.1007","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8921-398X","authenticated-orcid":false,"given":"Chimi","family":"Wangmo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lena","family":"Wiese","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,3]]},"reference":[{"key":"3006_CR1","unstructured":"AIDS. 2004. https:\/\/wiki.nci.nih.gov\/display\/NCIDTPdata\/AIDS+Antiviral+Screen+Data. 26 Jul 2023"},{"key":"3006_CR2","doi-asserted-by":"crossref","unstructured":"Angriman E, van der Grinten A, Hamann M, et al. Algorithms for large-scale network analysis and the NetworKit toolkit. In: Algorithms for big data. Lecture notes in computer science, vol. 13201. Berlin: Springer; 2022. p. 3\u201320.","DOI":"10.1007\/978-3-031-21534-6_1"},{"key":"3006_CR3","unstructured":"Ayed R. Aggregated search in distributed graph databases. (recherche d\u2019information agr\u00e9gative dans des bases de graphes distribu\u00e9es). PhD thesis, University of Lyon, France. 2019. https:\/\/tel.archives-ouvertes.fr\/tel-02520460."},{"issue":"9","key":"3006_CR4","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1109\/12.537122","volume":"45","author":"B Bollig","year":"1996","unstructured":"Bollig B, Wegener I. Improving the variable ordering of OBDDs is NP-complete. IEEE Trans Comput. 1996;45(9):993\u20131002. https:\/\/doi.org\/10.1109\/12.537122.","journal-title":"IEEE Trans Comput"},{"key":"3006_CR5","doi-asserted-by":"publisher","unstructured":"Bonnici V, Ferro A, Giugno R, et\u00a0al. Enhancing graph database indexing by suffix tree structure. In: Dijkstra T, Tsivtsivadze E, Marchiori E, et\u00a0al., editors. Pattern recognition in bioinformatics\u20145th IAPR international conference, PRIB 2010, Nijmegen, The Netherlands, September 22\u201324, 2010. Proceedings. Lecture notes in computer science, vol. 6282. Berlin: Springer; 2010. p. 195\u2013203. https:\/\/doi.org\/10.1007\/978-3-642-16001-1_17.","DOI":"10.1007\/978-3-642-16001-1_17"},{"key":"3006_CR6","doi-asserted-by":"publisher","unstructured":"Burch JR, Clarke EM, McMillan KL, et\u00a0al. Symbolic model checking: 10$$^20$$ states and beyond. In: Proceedings of the fifth annual symposium on logic in computer science (LICS \u201990), Philadelphia, Pennsylvania, USA, June 4\u20137, 1990. IEEE Computer Society; 1990. p. 428\u201339. https:\/\/doi.org\/10.1109\/LICS.1990.113767.","DOI":"10.1109\/LICS.1990.113767"},{"key":"3006_CR7","doi-asserted-by":"publisher","unstructured":"Cook SA. The complexity of theorem-proving procedures. In: Harrison MA, Banerji RB, Ullman JD, editors. Proceedings of the 3rd annual ACM symposium on theory of computing, May 3\u20135, 1971, Shaker Heights, Ohio, USA. ACM; 1971. p. 151\u20138. https:\/\/doi.org\/10.1145\/800157.805047.","DOI":"10.1145\/800157.805047"},{"key":"3006_CR8","doi-asserted-by":"publisher","unstructured":"Giugno R, Shasha, DE. GraphGrep: a fast and universal method for querying graphs. In: 16th International conference on pattern recognition, ICPR 2002, Quebec, Canada, August 11\u201315, 2002. IEEE Computer Society; 2002. p. 112\u20135. https:\/\/doi.org\/10.1109\/ICPR.2002.1048250.","DOI":"10.1109\/ICPR.2002.1048250"},{"issue":"10","key":"3006_CR9","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0076911","volume":"8","author":"R Giugno","year":"2013","unstructured":"Giugno R, Bonnici V, Bombieri N, et al. Grapes: a software for parallel searching on biological graphs targeting multi-core architectures. PLoS One. 2013;8(10):e76911.","journal-title":"PLoS One"},{"issue":"12","key":"3006_CR10","doi-asserted-by":"publisher","first-page":"1861","DOI":"10.14778\/3137765.3137794","volume":"10","author":"K Huang","year":"2017","unstructured":"Huang K, Bhowmick SS, Zhou S, et al. PICASSO: exploratory search of connected subgraph substructures in graph databases. Proc VLDB Endow. 2017;10(12):1861\u20134. https:\/\/doi.org\/10.14778\/3137765.3137794.","journal-title":"Proc VLDB Endow"},{"key":"3006_CR11","doi-asserted-by":"publisher","unstructured":"Jin C, Bhowmick SS, Choi B, et\u00a0al. PRAGUE: towards blending practical visual subgraph query formulation and query processing. In: Kementsietsidis A, Salles MAV, editors. IEEE 28th international conference on data engineering (ICDE 2012), Washington, DC, USA (Arlington, Virginia), 1\u20135 April, 2012. IEEE Computer Society; 2012. p. 222\u201333. https:\/\/doi.org\/10.1109\/ICDE.2012.49.","DOI":"10.1109\/ICDE.2012.49"},{"key":"3006_CR12","unstructured":"Katsarou F. Improving the performance and scalability of pattern subgraph queries. PhD thesis, University of Glasgow, UK. 2018.https:\/\/ethos.bl.uk\/OrderDetails.do?uin=uk.bl.ethos.744127."},{"issue":"12","key":"3006_CR13","doi-asserted-by":"publisher","first-page":"1566","DOI":"10.14778\/2824032.2824054","volume":"8","author":"F Katsarou","year":"2015","unstructured":"Katsarou F, Ntarmos N, Triantafillou P. Performance and scalability of indexed subgraph query processing methods. Proc VLDB Endow. 2015;8(12):1566\u201377. https:\/\/doi.org\/10.14778\/2824032.2824054.","journal-title":"Proc VLDB Endow"},{"key":"3006_CR14","doi-asserted-by":"publisher","unstructured":"Kim H, Choi Y, Park K, et\u00a0al. Versatile equivalences: speeding up subgraph query processing and subgraph matching. In: Li G, Li Z, Idreos S, et\u00a0al., editors. SIGMOD \u201921: international conference on management of data, virtual event, China, June 20\u201325, 2021. ACM; 2021. p. 925\u201337. https:\/\/doi.org\/10.1145\/3448016.3457265.","DOI":"10.1145\/3448016.3457265"},{"key":"3006_CR15","doi-asserted-by":"publisher","unstructured":"Klein K, Kriege NM, Mutzel P. CT-index: fingerprint-based graph indexing combining cycles and trees. In: Abiteboul S, B\u00f6hm K, Koch C, et\u00a0al., editors. Proceedings of the 27th international conference on data engineering, ICDE 2011, April 11\u201316, 2011, Hannover, Germany. IEEE Computer Society; 2011. p. 1115\u201326. https:\/\/doi.org\/10.1109\/ICDE.2011.5767909.","DOI":"10.1109\/ICDE.2011.5767909"},{"key":"3006_CR16","doi-asserted-by":"publisher","unstructured":"Kuntal BK, Dutta A, Mande SS. CompNet: a {GUI} based tool for comparison of multiple biological interaction networks. BMC Bioinform. 2019;17:185. https:\/\/doi.org\/10.1186\/s12859-016-1013-x","DOI":"10.1186\/s12859-016-1013-x"},{"issue":"1","key":"3006_CR17","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.datak.2009.08.006","volume":"69","author":"D Lemire","year":"2010","unstructured":"Lemire D, Kaser O, Aouiche K. Sorting improves word-aligned bitmap indexes. Data Knowl Eng. 2010;69(1):3\u201328. https:\/\/doi.org\/10.1016\/j.datak.2009.08.006.","journal-title":"Data Knowl Eng"},{"issue":"1","key":"3006_CR18","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1186\/s12859-021-04129-0","volume":"22","author":"N Licheri","year":"2021","unstructured":"Licheri N, Bonnici V, Beccuti M, et al. GRAPES-DD: exploiting decision diagrams for index-driven search in biological graph databases. BMC Bioinform. 2021;22(1):209. https:\/\/doi.org\/10.1186\/s12859-021-04129-0.","journal-title":"BMC Bioinform"},{"key":"3006_CR19","doi-asserted-by":"publisher","unstructured":"Luaces D, Viqueira JRR, Pena TF, et\u00a0al. Leveraging bitmap indexing for subgraph searching. In: Herschel M, Galhardas H, Reinwald B, et\u00a0al., editors. Advances in database technology\u201422nd international conference on extending database technology, EDBT 2019, Lisbon, Portugal, March 26\u201329, 2019. OpenProceedings.org; 2019. p. 49\u201360. https:\/\/doi.org\/10.5441\/002\/EDBT.2019.06.","DOI":"10.5441\/002\/EDBT.2019.06"},{"key":"3006_CR20","doi-asserted-by":"publisher","DOI":"10.14279\/tuj.eceasst.1.85","author":"T Meinl","year":"2006","unstructured":"Meinl T, W\u00f6rlein M, Urzova O, et al. The ParMol package for frequent subgraph mining. Electron Commun Eur Assoc Softw Sci Technol. 2006. https:\/\/doi.org\/10.14279\/tuj.eceasst.1.85.","journal-title":"Electron Commun Eur Assoc Softw Sci Technol"},{"issue":"5594","key":"3006_CR21","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo R, Shen-Orr S, Itzkovitz S, et al. Network motifs: simple building blocks of complex networks. Science. 2002;298(5594):824\u20137.","journal-title":"Science"},{"issue":"17","key":"3006_CR22","doi-asserted-by":"publisher","first-page":"2200159","DOI":"10.1002\/pmic.202200159","volume":"23","author":"Y Mohseni Behbahani","year":"2023","unstructured":"Mohseni Behbahani Y, Saighi P, Corsi F, et al. LEVELNET to visualize, explore, and compare protein-protein interaction networks. Proteomics. 2023;23(17):2200159.","journal-title":"Proteomics"},{"key":"3006_CR23","unstructured":"National Library of Medicine. 2021. PubChem data. https:\/\/pubchem.ncbi.nlm.nih.gov\/docs\/downloads."},{"key":"3006_CR24","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/128_2011_265","volume":"317","author":"E Valkov","year":"2012","unstructured":"Valkov E, Sharpe T, Marsh M, Greive S, Hyv\u00f6nen M. Targeting protein-protein interactions and fragment-based drug discovery. Top Curr Chem. 2012;317:145\u201379. https:\/\/doi.org\/10.1007\/128_2011_265","journal-title":"Top Curr Chem."},{"issue":"5","key":"3006_CR25","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1007\/S00778-020-00601-0","volume":"29","author":"C Wang","year":"2020","unstructured":"Wang C, Xie M, Bhowmick SS, et al. FERRARI: an efficient framework for visual exploratory subgraph search in graph databases. VLDB J. 2020;29(5):973\u201398. https:\/\/doi.org\/10.1007\/S00778-020-00601-0.","journal-title":"VLDB J"},{"key":"3006_CR26","doi-asserted-by":"publisher","unstructured":"Wangmo C, Wiese L. Efficient subgraph indexing for biochemical graphs. In: Cuzzocrea A, Gusikhin O, van\u00a0der Aalst WMP, et\u00a0al., editors. Proceedings of the 11th international conference on data science, technology and applications, DATA 2022, Lisbon, Portugal, July 11\u201313, 2022. SCITEPRESS; 2022. p. 533\u201340. https:\/\/doi.org\/10.5220\/0011350100003269.","DOI":"10.5220\/0011350100003269"},{"key":"3006_CR27","unstructured":"Wangmo C, Wiese L. SuMExplorer: summarisation-based frequent subgraph mining for visual exploratory subgraph searching. In: Leyer M, Wichmann J, editors. Lernen, Wissen, Daten, Analysen (LWDA) conference proceedings, Marburg, Germany, October 9\u201311, 2023, CEUR workshop proceedings, vol. 3630. CEUR-WS.org; 2023. p. 110\u201320. https:\/\/ceur-ws.org\/Vol-3630\/LWDA2023-paper10.pdf."},{"key":"3006_CR28","doi-asserted-by":"publisher","unstructured":"Yan X, Han J. gspan: Graph-based substructure pattern mining. In: Proceedings of the 2002 IEEE international conference on data mining (ICDM 2002), 9\u201312 December 2002, Maebashi City, Japan. IEEE Computer Society; 2002. p. 721\u20134. https:\/\/doi.org\/10.1109\/ICDM.2002.1184038.","DOI":"10.1109\/ICDM.2002.1184038"},{"key":"3006_CR29","doi-asserted-by":"publisher","unstructured":"Yan X, Yu PS, Han J. Graph indexing: a frequent structure-based approach. In: Weikum G, K\u00f6nig AC, De\u00dfloch S, editors. Proceedings of the ACM SIGMOD international conference on management of data, Paris, France, June 13\u201318, 2004. ACM; 2004. p. 335\u201346. https:\/\/doi.org\/10.1145\/1007568.1007607.","DOI":"10.1145\/1007568.1007607"},{"issue":"16","key":"3006_CR30","doi-asserted-by":"publisher","first-page":"5934","DOI":"10.1073\/pnas.0306752101","volume":"101","author":"E Yeger-Lotem","year":"2004","unstructured":"Yeger-Lotem E, Sattath S, Kashtan N, et al. Network motifs in integrated cellular networks of transcription-regulation and protein\u2013protein interaction. Proc Natl Acad Sci. 2004;101(16):5934\u20139.","journal-title":"Proc Natl Acad Sci"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-024-03006-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-024-03006-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-024-03006-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T07:03:14Z","timestamp":1719990194000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-024-03006-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,3]]},"references-count":30,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2024,8]]}},"alternative-id":["3006"],"URL":"https:\/\/doi.org\/10.1007\/s42979-024-03006-w","relation":{},"ISSN":["2661-8907"],"issn-type":[{"type":"electronic","value":"2661-8907"}],"subject":[],"published":{"date-parts":[[2024,7,3]]},"assertion":[{"value":"23 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest. This manuscript has not been submitted to, nor is under review at, another journal or other publishing venue.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics Approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to Participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}}],"article-number":"693"}}