{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:22:35Z","timestamp":1758273755995},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,2]]},"abstract":"\n Node similarity is fundamental in graph analytics. However, node similarity between nodes in different graphs (inter-graph nodes) has not received enough attention yet. The inter-graph node similarity is important in learning a new graph based on the knowledge extracted from an existing graph (transfer learning on graphs) and has applications in biological, communication, and social networks. In this paper, we propose a novel distance function for measuring inter-graph <u>n<\/u>ode similarity with <u>e<\/u>dit <u>d<\/u>istance, called\n NED<\/jats:bold>\n . In NED, two nodes are compared according to their local neighborhood topologies which are represented as unordered\n k<\/jats:italic>\n -adjacent trees, without relying on any extra information. Due to the hardness of computing tree edit distance on unordered trees which is NP-Complete, we propose a modified tree edit distance, called\n TED*<\/jats:bold>\n , for comparing unordered and unlabeled\n k<\/jats:italic>\n -adjacent trees. TED* is a metric distance, as the original tree edit distance, but more importantly, TED* is polynomially computable. As a metric distance, NED admits efficient indexing, provides interpretable results, and shows to perform better than existing approaches on a number of data analysis tasks, including graph deanonymization. Finally, the efficiency and effectiveness of NED are empirically demonstrated using real-world graphs.\n <\/jats:p>","DOI":"10.14778\/3055330.3055336","type":"journal-article","created":{"date-parts":[[2017,3,15]],"date-time":"2017-03-15T14:27:29Z","timestamp":1489588049000},"page":"697-708","source":"Crossref","is-referenced-by-count":2,"title":["NED"],"prefix":"10.14778","volume":"10","author":[{"given":"Haohan","family":"Zhu","sequence":"first","affiliation":[{"name":"Facebook Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xianrui","family":"Meng","sequence":"additional","affiliation":[{"name":"Apple Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Kollios","sequence":"additional","affiliation":[{"name":"Boston University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13672-6_40"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453903"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492517.2492582"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144502415960"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu307"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv026"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020512"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_9_1","volume-title":"Graph data anonymization, de-anonymization attacks, and de-anonymizability quantification: A survey","author":"Ji S.","year":"2016","unstructured":"S. Ji , P. Mittal , and R. Beyah . Graph data anonymization, de-anonymization attacks, and de-anonymizability quantification: A survey . IEEE Communications Surveys Tutorials , PP(99), 2016 . S. Ji, P. Mittal, and R. Beyah. Graph data anonymization, de-anonymization attacks, and de-anonymizability quantification: A survey. IEEE Communications Surveys Tutorials, PP(99), 2016."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020561"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989418"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448952"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2824443"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_15_1","volume-title":"June","author":"Leskovec J.","year":"2014","unstructured":"J. Leskovec and A. Krevl . SNAP Datasets: Stanford large network dataset collection , June 2014 . J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection, June 2014."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.194"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv130"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11815921_17"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2095686.2095692"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth436"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.imavis.2008.04.004"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2665943.2665960"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078187"},{"key":"e_1_2_1_24_1","first-page":"488","volume-title":"AISTATS","author":"Shervashidze N.","year":"2009","unstructured":"N. Shervashidze , S. V. N. Vishwanathan , T. Petri , K. Mehlhorn , and K. M. Borgwardt . Efficient graphlet kernels for large graph comparison . In AISTATS , pages 488 -- 495 , 2009 . N. Shervashidze, S. V. N. Vishwanathan, T. Petri, K. Mehlhorn, and K. M. Borgwardt. Efficient graphlet kernels for large graph comparison. In AISTATS, pages 488--495, 2009."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402736"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322143"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.70"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.28"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281280"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732221"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687631"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90062-0"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90136-J"},{"key":"e_1_2_1_34_1","volume-title":"NED: An inter-graph node metric on edit distance. CoRR, abs\/1602.02358","author":"Zhu H.","year":"2016","unstructured":"H. Zhu , X. Meng , and G. Kollios . NED: An inter-graph node metric on edit distance. CoRR, abs\/1602.02358 , 2016 . H. Zhu, X. Meng, and G. Kollios. NED: An inter-graph node metric on edit distance. CoRR, abs\/1602.02358, 2016."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3055330.3055336","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:08:10Z","timestamp":1672222090000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3055330.3055336"}},"subtitle":["an inter-graph <u>n<\/u>ode metric based on <u>e<\/u>dit <u>d<\/u>istance"],"short-title":[],"issued":{"date-parts":[[2017,2]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["10.14778\/3055330.3055336"],"URL":"https:\/\/doi.org\/10.14778\/3055330.3055336","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,2]]}}}