{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T09:59:33Z","timestamp":1775815173345,"version":"3.50.1"},"reference-count":107,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:p>Subgraph querying is one of the most important primitives in many applications. Although the field is well studied for deterministic graphs, in many situations, the graphs are probabilistic in nature. In this paper, we address the problem of subgraph querying in large probabilistic labeled graphs. We employ a novel algorithmic framework, called ChiSeL, that uses the idea of statistical significance for approximate subgraph matching on uncertain graphs that have uncertainty in edges. For each candidate matching vertex in the target graph that matches a query vertex, we compute its statistical significance using the chi-squared statistic. The search algorithm then proceeds in a greedy manner by exploring the vertex neighbors having the largest chi-square score. In addition to edge uncertainty, we also show how ChiSeL can handle uncertainty in labels and\/or vertices. Experiments on large real-life graphs show the efficiency and effectiveness of our algorithm.<\/jats:p>","DOI":"10.14778\/3401960.3401964","type":"journal-article","created":{"date-parts":[[2021,3,10]],"date-time":"2021-03-10T19:15:14Z","timestamp":1615403714000},"page":"1654-1668","source":"Crossref","is-referenced-by-count":7,"title":["ChiSeL"],"prefix":"10.14778","volume":"13","author":[{"given":"Shubhangi","family":"Agarwal","sequence":"first","affiliation":[{"name":"Indian Institute of Technology, Kanpur, India"}]},{"given":"Sourav","family":"Dutta","sequence":"additional","affiliation":[{"name":"Huawei Research Centre, Dublin, Ireland"}]},{"given":"Arnab","family":"Bhattacharya","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Kanpur, India"}]}],"member":"320","published-online":{"date-parts":[[2021,3,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1898953.1899055"},{"issue":"2","key":"e_1_2_1_2_1","first-page":"15","article-title":"Managing Uncertainty","volume":"30","author":"Adar E.","year":"2007","unstructured":"E. Adar and C. Re . Managing Uncertainty in Social Networks. Data Engineering Bulletin , 30 ( 2 ): 15 -- 22 , 2007 . E. Adar and C. Re. Managing Uncertainty in Social Networks. Data Engineering Bulletin, 30(2):15--22, 2007.","journal-title":"Social Networks. Data Engineering Bulletin"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1738952"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2618243.2618259"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588574"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.2203804"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp196"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989307"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2004.11.867"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350254"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2898607.2898816"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12045-014-0029-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325956"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2830336"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247574"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/959242.959249"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001404003228"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-014-7142-1"},{"key":"e_1_2_1_23_1","first-page":"284","volume-title":"MIST: Top-k Approximate Sub-string Mining Using Triplet Statistical Significance. In European Conference on Information Retrieval (ECIR)","author":"Dutta S.","year":"2015","unstructured":"S. Dutta . MIST: Top-k Approximate Sub-string Mining Using Triplet Statistical Significance. In European Conference on Information Retrieval (ECIR) , pages 284 -- 290 , 2015 . S. Dutta. MIST: Top-k Approximate Sub-string Mining Using Triplet Statistical Significance. In European Conference on Information Retrieval (ECIR), pages 284--290, 2015."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13657-3_35"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4018\/978-1-61350-056-9.ch004"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3358126"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052561"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055337"},{"key":"e_1_2_1_29_1","first-page":"45","volume-title":"Matching Structure and Semantics: A Survey on Graph-based Pattern Matching. In Conference on Artificial Intelligence (AAAI)","author":"Gallagher B.","year":"2006","unstructured":"B. Gallagher . Matching Structure and Semantics: A Survey on Graph-based Pattern Matching. In Conference on Artificial Intelligence (AAAI) , pages 45 -- 53 , 2006 . B. Gallagher. Matching Structure and Semantics: A Survey on Graph-based Pattern Matching. In Conference on Artificial Intelligence (AAAI), pages 45--53, 2006."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth084"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0460-y"},{"key":"e_1_2_1_32_1","first-page":"112","volume-title":"GraphGrep: A Fast and Universal Method for Querying Graphs. In International Conference on Pattern Recognition (ICPR)","author":"Giugno R.","year":"2002","unstructured":"R. Giugno and D. Shasha . GraphGrep: A Fast and Universal Method for Querying Graphs. In International Conference on Pattern Recognition (ICPR) , pages 112 -- 115 , 2002 . R. Giugno and D. Shasha. GraphGrep: A Fast and Universal Method for Querying Graphs. In International Conference on Pattern Recognition (ICPR), pages 112--115, 2002."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-015-0358-9"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993451"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2013.11.029"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920901"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-008-0106-1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739084"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0376-y"},{"key":"e_1_2_1_40_1","first-page":"566","volume-title":"GString: A Novel Approach for Efficient Search in Graph Databases. In International Conference on Data Engineering (ICDE)","author":"Jiang H.","year":"2007","unstructured":"H. Jiang , H. Wang , P. S. Yu , and S. Zhou . GString: A Novel Approach for Efficient Search in Graph Databases. In International Conference on Data Engineering (ICDE) , pages 566 -- 575 , 2007 . H. Jiang, H. Wang, P. S. Yu, and S. Zhou. GString: A Novel Approach for Efficient Search in Graph Databases. In International Conference on Data Engineering (ICDE), pages 566--575, 2007."},{"issue":"25","key":"e_1_2_1_41_1","first-page":"9404","volume":"103","author":"Jiang R.","year":"2006","unstructured":"R. Jiang , Z. Tu , T. Chen , and F. Sun . Network Motif Identification in Stochastic Networks. Proceedings of the National Academy of Sciences , 103 ( 25 ): 9404 -- 9409 , 2006 . R. Jiang, Z. Tu, T. Chen, and F. Sun. Network Motif Identification in Stochastic Networks. Proceedings of the National Academy of Sciences, 103(25):9404--9409, 2006.","journal-title":"Network Motif Identification in Stochastic Networks. Proceedings of the National Academy of Sciences"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020569"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002941"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.02.018"},{"key":"e_1_2_1_45_1","first-page":"87","volume-title":"Mining Uncertain Graphs: An Overview. In International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)","author":"Kassiano V.","year":"2016","unstructured":"V. Kassiano , A. Gounaris , A. N. Papadopoulos , and K. Tsichlas . Mining Uncertain Graphs: An Overview. In International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD) , pages 87 -- 116 , 2016 . V. Kassiano, A. Gounaris, A. N. Papadopoulos, and K. Tsichlas. Mining Uncertain Graphs: An Overview. In International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD), pages 87--116, 2016."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkh411"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824133"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448952"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807261"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.243"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.01.019"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/645496.658027"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/1032649.1033500"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-005-0003-9"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129501003577"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.fss.2019.02.021"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0268-8"},{"key":"e_1_2_1_59_1","first-page":"181","volume-title":"International Conference on Extending Database Technology (EDBT)","author":"Li X.","year":"2018","unstructured":"X. Li , R. Cheng , Y. Fang , J. Hu , and S. Maniu . Scalable Evaluation of k-NN Queries on Large Uncertain Graphs . In International Conference on Extending Database Technology (EDBT) , pages 181 -- 192 , 2018 . X. Li, R. Cheng, Y. Fang, J. Hu, and S. Maniu. Scalable Evaluation of k-NN Queries on Large Uncertain Graphs. In International Conference on Extending Database Technology (EDBT), pages 181--192, 2018."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2518683"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl287"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.11"},{"issue":"4","key":"e_1_2_1_63_1","first-page":"494","article-title":"Large Scale Graph Matching (LSGM): Techniques, Tools","volume":"8","author":"Mahmood A.","year":"2017","unstructured":"A. Mahmood , H. Farooq , and J. Ferzund . Large Scale Graph Matching (LSGM): Techniques, Tools , Applications and Challenges. International Journal of Advanced Computer Science and Applications , 8 ( 4 ): 494 -- 499 , 2017 . A. Mahmood, H. Farooq, and J. Ferzund. Large Scale Graph Matching (LSGM): Techniques, Tools, Applications and Challenges. International Journal of Advanced Computer Science and Applications, 8(4):494--499, 2017.","journal-title":"Applications and Challenges. International Journal of Advanced Computer Science and Applications"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3044713"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.842269"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.5555\/2886521.2886641"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3191513"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021972001000477X"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816710"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1951365.1951408"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593668"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920967"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.2307\/1403582"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4578-0"},{"key":"e_1_2_1_75_1","first-page":"7","article-title":"Learning a Health Knowledge Graph from Electronic Medical Records","author":"Rotmensch M.","year":"2017","unstructured":"M. Rotmensch , Y. Halpern , A. Tlimat , S. Horng , and D. Sontag . Learning a Health Knowledge Graph from Electronic Medical Records . Nature Scientific Rep. , 7 , 2017 . M. Rotmensch, Y. Halpern, A. Tlimat, S. Horng, and D. Sontag. Learning a Health Knowledge Graph from Electronic Medical Records. Nature Scientific Rep., 7, 2017.","journal-title":"Nature Scientific Rep."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336677"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0806627105"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32049-6_18"},{"key":"e_1_2_1_80_1","first-page":"220","volume-title":"Scaling Up Subgraph Query Proc. with Efficient Subgraph Matching. In International Conference on Data Engineering (ICDE)","author":"Sun S.","year":"2019","unstructured":"S. Sun and Q. Luo . Scaling Up Subgraph Query Proc. with Efficient Subgraph Matching. In International Conference on Data Engineering (ICDE) , pages 220 -- 231 , 2019 . S. Sun and Q. Luo. Scaling Up Subgraph Query Proc. with Efficient Subgraph Matching. In International Conference on Data Engineering (ICDE), pages 220--231, 2019."},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl571"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497505"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150448"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281271"},{"key":"e_1_2_1_85_1","volume-title":"Error-correcting Isomorphisms of Attributed Relational Graphs for Pattern Recognition. Transactions on Systems, Man, and Cybernetics, 9(12):757--768","author":"Tsai W. H.","year":"1979","unstructured":"W. H. Tsai and K. Fu . Error-correcting Isomorphisms of Attributed Relational Graphs for Pattern Recognition. Transactions on Systems, Man, and Cybernetics, 9(12):757--768 , 1979 . W. H. Tsai and K. Fu. Error-correcting Isomorphisms of Attributed Relational Graphs for Pattern Recognition. Transactions on Systems, Man, and Cybernetics, 9(12):757--768, 1979."},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"issue":"3","key":"e_1_2_1_87_1","first-page":"410","article-title":"The Complexity of Enumeration and Reliability Prob","volume":"8","author":"Valiant L. G.","year":"1979","unstructured":"L. G. Valiant . The Complexity of Enumeration and Reliability Prob . J. of Computing , 8 ( 3 ): 410 -- 421 , 1979 . L. G. Valiant. The Complexity of Enumeration and Reliability Prob. J. of Computing, 8(3):410--421, 1979.","journal-title":"J. of Computing"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68204-4_23"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.5555\/844380.844811"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114248"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066244"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339765"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2661868"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2015.12.034"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311908"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0373-y"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402726"},{"key":"e_1_2_1_98_1","first-page":"34","volume-title":"Probabilistic Graph and Hypergraph Matching. In Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Zass R.","year":"2008","unstructured":"R. Zass and A. Shashua . Probabilistic Graph and Hypergraph Matching. In Conference on Computer Vision and Pattern Recognition (CVPR) , pages 34 -- 41 , 2008 . R. Zass and A. Shashua. Probabilistic Graph and Hypergraph Matching. In Conference on Computer Vision and Pattern Recognition (CVPR), pages 34--41, 2008."},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687631"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516385"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516384"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920988"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.1145\/1316874.1316897"},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353369"},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031453.1031462"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835885"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3401960.3401964","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:10:41Z","timestamp":1672225841000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3401960.3401964"}},"subtitle":["graph similarity search using chi-squared statistics in large probabilistic graphs"],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":107,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["10.14778\/3401960.3401964"],"URL":"https:\/\/doi.org\/10.14778\/3401960.3401964","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,6]]}}}