{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T20:43:21Z","timestamp":1776113001876,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>Graph data have become ubiquitous and manipulating them based on similarity is essential for many applications. Graph edit distance is one of the most widely accepted measures to determine similarities between graphs and has extensive applications in the fields of pattern recognition, computer vision etc. Unfortunately, the problem of graph edit distance computation is NP-Hard in general. Accordingly, in this paper we introduce three novel methods to compute the upper and lower bounds for the edit distance between two graphs in polynomial time. Applying these methods, two algorithms AppFull and AppSub are introduced to perform different kinds of graph search on graph databases. Comprehensive experimental studies are conducted on both real and synthetic datasets to examine various aspects of the methods for bounding graph edit distance. Result shows that these methods achieve good scalability in terms of both the number of graphs and the size of graphs. The effectiveness of these algorithms also confirms the usefulness of using our bounds in filtering and searching of graphs.<\/jats:p>","DOI":"10.14778\/1687627.1687631","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"25-36","source":"Crossref","is-referenced-by-count":276,"title":["Comparing stars"],"prefix":"10.14778","volume":"2","author":[{"given":"Zhiping","family":"Zeng","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, P.R. China"}]},{"given":"Anthony K. H.","family":"Tung","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]},{"given":"Jianyong","family":"Wang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, P.R. China"}]},{"given":"Jianhua","family":"Feng","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, P.R. China"}]},{"given":"Lizhu","family":"Zhou","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, P.R. China"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.211474"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083630"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164150"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.954600"},{"key":"e_1_2_1_5_1","volume-title":"ICDM '02","author":"Borgelt C.","unstructured":"C. Borgelt and M. R. Berthold . Mining molecular fragments: Finding relevant substructures of molecules . In ICDM '02 . C. Borgelt and M. R. Berthold. Mining molecular fragments: Finding relevant substructures of molecules. In ICDM '02."},{"key":"e_1_2_1_6_1","volume-title":"Computational Modeling of Genetic and Biochemical Networks (Computational Molecular Biology)","author":"Bower J. M.","year":"2004","unstructured":"J. M. Bower and H. Bolouri . Computational Modeling of Genetic and Biochemical Networks (Computational Molecular Biology) . 2004 . J. M. Bower and H. Bolouri. Computational Modeling of Genetic and Biochemical Networks (Computational Molecular Biology). 2004."},{"key":"e_1_2_1_7_1","volume-title":"WWW '00","author":"Broder A.","unstructured":"A. Broder , R. Kumar , F. Maghoul , P. Raghavan , S. Rajagopalan , R. Stata , A. Tomkins , and J. Wiener . Graph structure in the web: experiments and models . In WWW '00 . A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web: experiments and models. In WWW '00."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(97)00179-7"},{"key":"e_1_2_1_9_1","volume-title":"VLDB '07","author":"Chen C.","unstructured":"C. Chen , X. Yan , P. S. Yu , J. Han , D.-Q. Zhang , and X. Gu . Towards graph containment search and indexing . In VLDB '07 . C. Chen, X. Yan, P. S. Yu, J. Han, D.-Q. Zhang, and X. Gu. Towards graph containment search and indexing. In VLDB '07."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(01)00017-4"},{"key":"e_1_2_1_11_1","volume-title":"Computers and Intractability","author":"Garey M. R.","year":"1990","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability ; A Guide to the Theory of NP-Completeness . 1990 . M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. 1990."},{"issue":"2","key":"e_1_2_1_12_1","first-page":"100","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart P.","year":"1968","unstructured":"P. Hart , N. Nilsson , and B. Raphael . A formal basis for the heuristic determination of minimum cost paths . IEEE Trans. SSC , 4 ( 2 ): 100 -- 107 , 1968 . P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. SSC, 4(2):100--107, 1968.","journal-title":"IEEE Trans. SSC"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.37"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247516"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti1049"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.152"},{"key":"e_1_2_1_17_1","volume-title":"VLDB '05","author":"Kacholia V.","unstructured":"V. Kacholia , S. Pandit , S. Chakrabarti , S. Sudarshan , R. Desai , and H. Karambelkar . Bidirectional expansion for keyword search on graph databases . In VLDB '05 . V. Kacholia, S. Pandit, S. Chakrabarti, S. Sudarshan, R. Desai, and H. Karambelkar. Bidirectional expansion for keyword search on graph databases. In VLDB '05."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_1_19_1","volume-title":"ICDM '01","author":"Kuramochi M.","unstructured":"M. Kuramochi and G. Karypis . Frequent subgraph discovery . In ICDM '01 . M. Kuramochi and G. Karypis. Frequent subgraph discovery. In ICDM '01."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.682179"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.862201"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11815921_17"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.599932"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/45.6.631"},{"key":"e_1_2_1_25_1","volume-title":"MLG '07","author":"Riesen K.","unstructured":"K. Riesen , S. Fankhauser , and H. Bunke . Speeding up graph edit distance computation with a bipartite heuristic . In MLG '07 . K. Riesen, S. Fankhauser, and H. Bunke. Speeding up graph edit distance computation with a bipartite heuristic. In MLG '07."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543620"},{"key":"e_1_2_1_27_1","volume-title":"VLDB '03","author":"Srinivasa S.","unstructured":"S. Srinivasa and S. Kumar . A platform based on the multi-dimensional data modal for analysis of bio-molecular structures . In VLDB '03 . S. Srinivasa and S. Kumar. A platform based on the multi-dimensional data modal for analysis of bio-molecular structures. In VLDB '03."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl571"},{"key":"e_1_2_1_29_1","volume-title":"Computational Chemical Graph Theory: Characterization, Enumeration and Generation of Chemical Structures by Computer Methods","author":"Trinajstic N.","year":"1991","unstructured":"N. Trinajstic , J. V. Knop , W. R. Muller , K. Syzmanski , and S. Nikolic . Computational Chemical Graph Theory: Characterization, Enumeration and Generation of Chemical Structures by Computer Methods . 1991 . N. Trinajstic, J. V. Knop, W. R. Muller, K. Syzmanski, and S. Nikolic. Computational Chemical Graph Theory: Characterization, Enumeration and Generation of Chemical Structures by Computer Methods. 1991."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247573"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci9800211"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.601251"},{"key":"e_1_2_1_33_1","volume-title":"ICDM'02","author":"Yan X.","unstructured":"X. Yan and J. Han . gspan: Graph-based substructure pattern mining . In ICDM'02 . X. Yan and J. Han. gspan: Graph-based substructure pattern mining. In ICDM'02."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189769.1189777"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066243"},{"key":"e_1_2_1_37_1","volume-title":"VLDB '07","author":"Zhao P.","unstructured":"P. Zhao , J. X. Yu , and P. S. Yu . Graph indexing: Tree + delta &gt;= graph . In VLDB '07 . P. Zhao, J. X. Yu, and P. S. Yu. Graph indexing: Tree + delta &gt;= graph. In VLDB '07."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687631","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:23:05Z","timestamp":1672226585000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687631"}},"subtitle":["on approximating graph edit distance"],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687631"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687631","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}