{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:11:22Z","timestamp":1760235082624,"version":"build-2065373602"},"reference-count":47,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T00:00:00Z","timestamp":1627344000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Subgraph and supergraph search methods are promising techniques for the development of new drugs. For example, the chemical structure of favipiravir\u2014an antiviral treatment for influenza\u2014resembles the structure of some components of RNA. Represented as graphs, such compounds are similar to a subgraph of favipiravir. However, the existing supergraph search methods can only discover compounds that match exactly. We propose a novel problem, called similar supergraph search, and design an efficient algorithm to solve it. The problem is to identify all graphs in a database that are similar to any subgraph of a query graph, where similarity is defined as edit distance. Our algorithm represents the set of candidate subgraphs by a code tree, which it uses to efficiently compute edit distance. With a distance threshold of zero, our algorithm is equivalent to an existing efficient algorithm for exact supergraph search. Our experiments show that the computation time increased exponentially as the distance threshold increased, but increased sublinearly with the number of graphs in the database.<\/jats:p>","DOI":"10.3390\/a14080225","type":"journal-article","created":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T12:18:31Z","timestamp":1627388311000},"page":"225","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Similar Supergraph Search Based on Graph Edit Distance"],"prefix":"10.3390","volume":"14","author":[{"given":"Masataka","family":"Yamada","sequence":"first","affiliation":[{"name":"Graduate School of Science and Technology, Kwansei Gakuin University, 2-1 Gakuen, Sanda 669-1337, Japan"}]},{"given":"Akihiro","family":"Inokuchi","sequence":"additional","affiliation":[{"name":"Graduate School of Science and Technology, Kwansei Gakuin University, 2-1 Gakuen, Sanda 669-1337, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2021,7,27]]},"reference":[{"key":"ref_1","first-page":"25","article-title":"Characteristics of a candidate of an antiviral medication against COVID-19","volume":"5005","author":"Shiraki","year":"2020","journal-title":"Jpn. Med. J."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Bonnici, V., Ferro, A., Giugno, R., Pulvirenti, A., and Shasha, D.E. (2010, January 22\u201324). Enhancing Graph Database Indexing by Suffix Tree Structure. Proceedings of the IAPR International Conference on Pattern Recognition in Bioinformatics, Nijmegen, The Netherlands.","DOI":"10.1007\/978-3-642-16001-1_17"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Cheng, J., Ke, Y., Ng, W., and Lu, A. (2007, January 11\u201314). FG-Index: Towards Verification-Free Query Processing on Graph Databases. Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, China.","DOI":"10.1145\/1247480.1247574"},{"key":"ref_4","first-page":"48","article-title":"Efficient Query Processing on Graph Databases","volume":"2","author":"Cheng","year":"2009","journal-title":"ACM Trans. Database Syst."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Klein, K., Kriege, N.M., and Mutzel, P. (2011, January 11\u201316). CT-Index: Fingerprint-based Graph Indexing Combining Cycles and Trees. Proceedings of the IEEE International Conference on Data Engineering, Hannover, Germany.","DOI":"10.1109\/ICDE.2011.5767909"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"364","DOI":"10.14778\/1453856.1453899","article-title":"Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism","volume":"1","author":"Shang","year":"2008","journal-title":"Proc. Vldb Endow."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Sun, S., and Luo, Q. (2019, January 16\u201319). Scaling Up Subgraph Query Processing with Efficient Subgraph Matching. Proceedings of the IEEE International Conference on Data Engineering, Paris, France.","DOI":"10.1109\/ICDE.2019.00028"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Williams, D.W., Huan, J., and Wang, W. (2007, January 17\u201320). Graph Database Indexing Using Structured Graph Decomposition. Proceedings of the IEEE International Conference on Data Engineering, Istanbul, Turkey.","DOI":"10.1109\/ICDE.2007.368956"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Xie, Y., and Yu, P.S. (2011, January 24\u201328). CP-Index: On the Efficient Indexing of Large Graphs. Proceedings of the ACM Conference on Information and Knowledge Management, Glasgow, UK.","DOI":"10.1145\/2063576.2063835"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Yan, X., Yu, P.S., and Han, J. (2004, January 13\u201318). Graph Indexing: A Frequent Structure-based Approach. Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France.","DOI":"10.1145\/1007568.1007607"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s00778-012-0284-8","article-title":"Lindex: A Lattice-based Index for Graph Databases","volume":"22","author":"Yuan","year":"2013","journal-title":"VLDB J."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Zhang, S., Hu, M., and Yang, J. (2007, January 17\u201320). TreePi: A Novel Graph Indexing Method. Proceedings of the IEEE International Conference on Data Engineering, Istanbul, Turkey.","DOI":"10.1109\/ICDE.2007.368955"},{"key":"ref_13","unstructured":"Zhao, P., Yu, J.X., and Yu, P.S. (2007, January 23\u201327). Graph Indexing: Tree + Delta >= Graph. Proceedings of the International Conference on Very Large Data Bases, Vienna, Austria."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Zou, L., Chen, L., Yu, J.X., and Lu, Y. (2008, January 25\u201329). A Novel Spectral Coding in a Large Graph Database. Proceedings of the International Conference on Extending Database Technology, Nantes, France.","DOI":"10.1145\/1353343.1353369"},{"key":"ref_15","unstructured":"Chen, C., Yan, X., Yu, P.S., Han, J., Zhang, D., and Gu, X. (2007, January 23\u201327). Towards Graph Containment Search and Indexing. Proceedings of the International Conference on Very Large Data Bases, Vienna, Austria."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/s00778-010-0212-8","article-title":"Fast Graph Query Processing with a Low-Cost Index","volume":"20","author":"Cheng","year":"2011","journal-title":"VLDB J."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1587\/transinf.2019EDP7011","article-title":"Efficient Supergraph Search Using Graph Coding","volume":"103-D","author":"Imai","year":"2020","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1456","DOI":"10.14778\/3397230.3397241","article-title":"IDAR: Fast Supergraph Search Using DAG Integration","volume":"13","author":"Kim","year":"2020","journal-title":"Proc. Vldb Endow."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Lyu, B., Qin, L., Lin, X., Chang, L., and Yu, J.X. (2016, January 16\u201320). Scalable Supergraph Search in Large Graph Databases. Proceedings of the IEEE International Conference on Data Engineering, Helsinki, Finland.","DOI":"10.1109\/ICDE.2016.7498237"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"829","DOI":"10.14778\/2536206.2536211","article-title":"Mining and Indexing Graphs for Supergraph Search","volume":"6","author":"Yuan","year":"2013","journal-title":"Proc. Vldb Endow."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Zhang, S., Li, J., Gao, H., and Zou, Z. (2009, January 24\u201326). A Novel Approach for Efficient Supergraph Query Processing on Graph Databases. Proceedings of the International Conference on Extending Database Technology, Saint-Petersburg, Russia.","DOI":"10.1145\/1516360.1516385"},{"key":"ref_22","unstructured":"Zhu, G., Lin, X., Zhang, W., Wang, W., and Shang, H. (July, January 30). PrefIndex: An Efficient Supergraph Containment Search Technique. Proceedings of the International Conference on Scientific and Statistical Database Management, Heidelberg, Germany."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Riesen, K. (2015). Structural Pattern Recognition with Graph Edit Distance\u2014Approximation Algorithms and Applications. Advances in Computer Vision and Pattern Recognition, Springer.","DOI":"10.1007\/978-3-319-27252-8"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Inokuchi, A., Washio, T., and Motoda, H. (2000, January 13\u201316). An Apriori-based Algorithm for Mining Frequent Substructures from Graph Data. Proceedings of the European Conference on Principles of Data Mining and Knowledge Discovery, Lyon, France.","DOI":"10.1007\/3-540-45372-5_2"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Chang, L., Feng, X., Lin, X., Qin, L., Zhang, W., and Ouyang, D. (2020, January 20\u201324). Speeding Up GED Verification for Graph Similarity Search. Proceedings of the IEEE International Conference on Data Engineering, Dallas, TX, USA.","DOI":"10.1109\/ICDE48307.2020.00074"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Gouda, K., and Hassaan, M. (2016, January 16\u201320). CS_GED: An Efficient Approach for Graph Edit Similarity Computation. Proceedings of the IEEE International Conference on Data Engineering, Helsinki, Finland.","DOI":"10.1109\/ICDE.2016.7498246"},{"key":"ref_27","unstructured":"Kim, J., Choi, D., and Li, C. (2019, January 26\u201329). Inves: Incremental Partitioning-based Verification for Graph Similarity Search. Proceedings of the International Conference on Extending Database Technology, Lisbon, Portugal."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Liang, Y., and Zhao, P. (2017, January 19\u201322). Similarity Search in Graph Databases: A Multi-Layered Indexing Approach. Proceedings of the IEEE International Conference on Data Engineering, San Diego, CA, USA.","DOI":"10.1109\/ICDE.2017.129"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Wang, X., Ding, X., Tung, A.K.H., Ying, S., and Jin, H. (2012, January 1\u20135). An Efficient Graph Indexing Method. Proceedings of the IEEE International Conference on Data Engineering, Arlington, VA, USA.","DOI":"10.1109\/ICDE.2012.28"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1007\/s00778-013-0306-1","article-title":"Efficient Processing of Graph Similarity Queries with Edit Distance Constraints","volume":"22","author":"Zhao","year":"2013","journal-title":"VLDB J."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s00778-017-0487-0","article-title":"Efficient Structure Similarity Searches: A Partition-based Approach","volume":"27","author":"Zhao","year":"2018","journal-title":"VLDB J."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1109\/TKDE.2014.2349924","article-title":"Efficient Graph Similarity Search Over Large Graph Databases","volume":"27","author":"Zheng","year":"2015","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_33","unstructured":"Inokuchi, A., Washio, T., Nishimura, Y., and Motoda, H. (2002). A Fast Algorithm for Mining Frequent Connected Subgraphs, IBM Research."},{"key":"ref_34","unstructured":"Yan, X., and Han, J. (2002, January 9\u201312). gSpan: Graph-Based Substructure Pattern Mining. Proceedings of the IEEE International Conference on Data Mining, Maebashi City, Japan."},{"key":"ref_35","unstructured":"Bi, F., Chang, L., Lin, X., Qin, L., and Zhang, W. (July, January 26). Efficient Subgraph Matching by Postponing Cartesian Products. Proceedings of the International Conference on Management of Data, San Francisco, CA, USA."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"788","DOI":"10.14778\/2311906.2311907","article-title":"Efficient Subgraph Matching on Billion Node Graphs","volume":"5","author":"Sun","year":"2012","journal-title":"Proc. Vldb Endow."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Zhang, S., Li, S., and Yang, J. (2009, January 24\u201326). GADDI: Distance Index based Subgraph Matching in Biological Networks. Proceedings of the International Conference on Extending Database Technology, Saint Petersburg, Russia.","DOI":"10.1145\/1516360.1516384"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Khan, A., Li, N., Yan, X., Guan, Z., Chakraborty, S., and Tao, S. (2011, January 12\u201316). Neighborhood based Fast Graph Search in Large Networks. Proceedings of the ACM SIGMOD International Conference on Management of Data, Athens, Greece.","DOI":"10.1145\/1989323.1989418"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Khan, A., Wu, Y., Aggarwal, C.C., and Yan, X. (2013). NeMa: Fast Graph Search with Label Similarity. Proc. Vldb Endow., 181\u2013192.","DOI":"10.14778\/2535569.2448952"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1093\/bioinformatics\/btl571","article-title":"SAGA: A Subgraph Matching Tool for Biological Graphs","volume":"23","author":"Tian","year":"2007","journal-title":"Bioinformatics"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.14778\/1920841.1920988","article-title":"SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs","volume":"3","author":"Zhang","year":"2010","journal-title":"Proc. Vldb Endow."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1561\/2200000076","article-title":"Graph Kernels: State-of-the-Art and Future Challenges","volume":"13","author":"Borgwardt","year":"2002","journal-title":"Found. Trends Mach. Learn."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Wang, X., Smalter, A.M., Huan, J., and Lushington, G.H. (2008, January 25\u201329). G-Hash: Towards Fast Kernel-based Similarity Search in Large Graph Databases. Proceedings of the International Conference on Extending Database Technology, Nantes, France.","DOI":"10.1145\/1516360.1516416"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1023\/A:1021271615909","article-title":"Maximum Common Subgraph Isomorphism Algorithms for the Matching of Chemical Structures","volume":"16","author":"Raymond","year":"2002","journal-title":"J. Comput. Aided Mol. Des."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"2523","DOI":"10.1016\/j.dam.2012.01.026","article-title":"The Maximum Common Edge Subgraph Problem: A Polyhedral Investigation","volume":"160","author":"Bahiense","year":"2012","journal-title":"Discret. Appl. Math."},{"key":"ref_46","unstructured":"Kashima, H., Tsuda, K., and Inokuchi, A. (2003, January 21\u201324). Marginalized Kernels Between Labeled Graphs. Proceedings of the International Conference on Machine Learning, Washington, DC, USA."},{"key":"ref_47","first-page":"2539","article-title":"Weisfeiler-Lehman Graph Kernels","volume":"12","author":"Shervashidze","year":"2011","journal-title":"J. Mach. Learn. Res."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/8\/225\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:35:35Z","timestamp":1760164535000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/8\/225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,27]]},"references-count":47,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,8]]}},"alternative-id":["a14080225"],"URL":"https:\/\/doi.org\/10.3390\/a14080225","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,7,27]]}}}