{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T11:12:27Z","timestamp":1769166747272,"version":"3.49.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,5]]},"abstract":"<jats:p>\n            Many studies have been conducted on seeking the efficient solution for subgraph similarity search over certain (deterministic) graphs due to its wide application in many fields, including bioinformatics, social network analysis, and Resource Description Framework (RDF) data management. All these works assume that the underlying data are certain. However, in reality, graphs are often noisy and uncertain due to various factors, such as errors in data extraction, inconsistencies in data integration, and privacy preserving purposes. Therefore, in this paper, we study subgraph similarity search on large probabilistic graph databases. Different from previous works assuming that edges in an uncertain graph are independent of each other, we study the uncertain graphs where edges' occurrences are correlated. We formally prove that subgraph similarity search over probabilistic graphs is #P-complete, thus, we employ a\n            <jats:italic>filter-and-verify<\/jats:italic>\n            framework to speed up the search. In the\n            <jats:italic>filtering<\/jats:italic>\n            phase, we develop tight lower and upper bounds of\n            <jats:italic>subgraph similarity probability<\/jats:italic>\n            based on a probabilistic matrix index, PMI. PMI is composed of discriminative subgraph features associated with tight lower and upper bounds of\n            <jats:italic>subgraph isomorphism probability<\/jats:italic>\n            . Based on PMI, we can sort out a large number of probabilistic graphs and maximize the pruning capability. During the\n            <jats:italic>verification<\/jats:italic>\n            phase, we develop an efficient sampling algorithm to validate the remaining candidates. The efficiency of our proposed solutions has been verified through extensive experiments.\n          <\/jats:p>","DOI":"10.14778\/2311906.2311908","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"800-811","source":"Crossref","is-referenced-by-count":62,"title":["Efficient subgraph similarity search on large probabilistic graph databases"],"prefix":"10.14778","volume":"5","author":[{"given":"Ye","family":"Yuan","sequence":"first","affiliation":[{"name":"Northeastern University, China"}]},{"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}]},{"given":"Haixun","family":"Wang","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2012,5]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"411","volume-title":"Proc. of VLDB","author":"Abadi D. J.","year":"2007","unstructured":"D. J. Abadi , A. Marcus , S. R. Madden , and K. Hollenbach . Scalable semantic web data management using vertical partitioning . In Proc. of VLDB , pages 411 -- 422 , 2007 . D. J. Abadi, A. Marcus, S. R. Madden, and K. Hollenbach. Scalable semantic web data management using vertical partitioning. In Proc. of VLDB, pages 411--422, 2007."},{"issue":"2","key":"e_1_2_1_2_1","first-page":"15","article-title":"Managing uncertainty in social networks","volume":"30","author":"Adar E.","year":"2007","unstructured":"E. Adar and C. Re . Managing uncertainty in social networks . IEEE Data Eng. Bull. , 30 ( 2 ): 15 -- 22 , 2007 . E. Adar and C. Re. Managing uncertainty in social networks. IEEE Data Eng. Bull., 30(2):15--22, 2007.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1513922"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1738952"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.2203804"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/nbt924"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01955041"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080091.1080108"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl145"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265531"},{"key":"e_1_2_1_12_1","volume-title":"PWS","author":"D. H.","year":"1997","unstructured":"D. H. (ed.). Approximation algorithms for NP-Hard problems . PWS , 1997 . D. H. (ed.). Approximation algorithms for NP-Hard problems. PWS, 1997."},{"key":"e_1_2_1_13_1","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and intractability: a guide to the theory of NP-completeness . W. H. Freeman , 1979 . M. R. Garey and D. S. Johnson. Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, 1979."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988727"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.37"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739084"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0888-613X(96)00069-2"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04409-0_32"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367902"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0507841103"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002941"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01074775"},{"key":"e_1_2_1_23_1","first-page":"1108","article-title":"Polynomial solvability of convex quadratic programming","volume":"20","author":"Kozlov M.","year":"1979","unstructured":"M. Kozlov , S. Tarasov , and L. Hacijan . Polynomial solvability of convex quadratic programming . Mathematics Doklady , 20 : 1108 -- 1111 , 1979 . M. Kozlov, S. Tarasov, and L. Hacijan. Polynomial solvability of convex quadratic programming. Mathematics Doklady, 20:1108--1111, 1979.","journal-title":"Mathematics Doklady"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989341"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956972"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1076315"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920967"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/30.5.1163"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447846"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066303"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"issue":"1","key":"e_1_2_1_33_1","first-page":"360","article-title":"A direct comparison of protein interaction confidence assignment schemes","volume":"7","author":"Suthram S.","year":"2006","unstructured":"S. Suthram , T. Shlomi , E. Ruppin , R. Sharan , and T. Ideker . A direct comparison of protein interaction confidence assignment schemes . Bioinformatics , 7 ( 1 ): 360 , 2006 . S. Suthram, T. Shlomi, E. Ruppin, R. Sharan, and T. Ideker. A direct comparison of protein interaction confidence assignment schemes. Bioinformatics, 7(1):360, 2006.","journal-title":"Bioinformatics"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.28"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368956"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956784"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066244"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12026-8_14"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402726"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687631"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835885"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.80"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2311906.2311908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:29:10Z","timestamp":1672223350000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2311906.2311908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5]]},"references-count":43,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2012,5]]}},"alternative-id":["10.14778\/2311906.2311908"],"URL":"https:\/\/doi.org\/10.14778\/2311906.2311908","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,5]]}}}