{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T06:28:38Z","timestamp":1791268118551,"version":"4.1.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>\n                    It is increasingly common to find real-life data represented as networks of labeled, heterogeneous entities. To query these networks, one often needs to identify the matches of a given query graph in a (typically large) network modeled as a target graph. Due to noise and the lack of fixed schema in the target graph, the query graph can substantially differ from its matches in the target graph in both structure and node labels, thus bringing challenges to the graph querying tasks. In this paper, we propose NeMa (Network Match), a neighborhood-based subgraph matching technique for querying real-life networks. (1) To measure the quality of the match, we propose a novel subgraph matching cost metric that aggregates the costs of matching individual nodes, and unifies both structure and node label similarities. (2) Based on the metric, we formulate the minimum cost subgraph matching problem. Given a query graph and a target graph, the problem is to identify the (top-\n                    <jats:italic>k<\/jats:italic>\n                    ) matches of the query graph with minimum costs in the target graph. We show that the problem is NP-hard, and also hard to approximate. (3) We propose a heuristic algorithm for solving the problem based on an inference model. In addition, we propose optimization techniques to improve the efficiency of our method. (4) We empirically verify that NeMa is both effective and efficient compared to the keyword search and various state-of-the-art graph querying techniques.\n                  <\/jats:p>","DOI":"10.14778\/2535569.2448952","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T08:17:57Z","timestamp":1403597877000},"page":"181-192","source":"Crossref","is-referenced-by-count":106,"title":["NeMa"],"prefix":"10.14778","volume":"6","author":[{"given":"Arijit","family":"Khan","sequence":"first","affiliation":[{"name":"Computer Science, University of California, Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yinghui","family":"Wu","sequence":"additional","affiliation":[{"name":"Computer Science, University of California, Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charu C.","family":"Aggarwal","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research, Hawthorne, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xifeng","family":"Yan","sequence":"additional","affiliation":[{"name":"Computer Science, University of California, Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,1]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"ICDT","author":"Abiteboul S.","year":"1997","unstructured":"S. Abiteboul . Querying Semi-Structured Data . ICDT , 1997 . S. Abiteboul. Querying Semi-Structured Data. ICDT, 1997."},{"key":"e_1_2_1_2_1","volume-title":"Verbal Learning and Verbal Behavior","author":"Anderson J. R.","year":"1983","unstructured":"J. R. Anderson . A Spreading Activation Theory of Memory. J . Verbal Learning and Verbal Behavior , 1983 . J. R. Anderson. A Spreading Activation Theory of Memory. J. Verbal Learning and Verbal Behavior, 1983."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989307"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.135"},{"key":"e_1_2_1_5_1","volume-title":"APCCM","author":"Berger H.","year":"2004","unstructured":"H. Berger , M. Dittenbach , and D. Merkl . An Adaptive Information Retrieval System based on Associative Networks . APCCM , 2004 . H. Berger, M. Dittenbach, and D. Merkl. An Adaptive Information Retrieval System based on Associative Networks. APCCM, 2004."},{"key":"e_1_2_1_6_1","author":"Buchan N.","year":"2004","unstructured":"N. Buchan and R. Croson . The Boundaries of Trust: Own and Others' Actions in US and China. J. Econ. Behav. and Org. , 2004 . N. Buchan and R. Croson. The Boundaries of Trust: Own and Others' Actions in US and China. J. Econ. Behav. and Org., 2004.","journal-title":"J. Econ. Behav. and Org."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458469.1458481"},{"key":"e_1_2_1_8_1","volume-title":"STOC","author":"Cook S.","year":"1971","unstructured":"S. Cook . The Complexity of Theorem Proving Procedures . STOC , 1971 . 10.1145\/800157.805047 S. Cook. The Complexity of Theorem Proving Procedures. STOC, 1971. 10.1145\/800157.805047"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_10_1","volume-title":"VLDB","author":"Das S.","year":"2004","unstructured":"S. Das , E. I. Chong , G. Eadon , and J. Srinivasan . Supporting Ontology-Based Semantic Matching in RDBMS . VLDB , 2004 . S. Das, E. I. Chong, G. Eadon, and J. Srinivasan. Supporting Ontology-Based Semantic Matching in RDBMS. VLDB, 2004."},{"key":"e_1_2_1_11_1","volume-title":"PVLDB","author":"Fan W.","year":"2010","unstructured":"W. Fan , J. Li , S. Ma , N. Tang , Y. Wu , and Y. Wu . Graph Pattern Matching: From Intractable to Polynomial Time . PVLDB , 2010 . W. Fan, J. Li, S. Ma, N. Tang, Y. Wu, and Y. Wu. Graph Pattern Matching: From Intractable to Polynomial Time. PVLDB, 2010."},{"key":"e_1_2_1_12_1","volume-title":"PVLDB","author":"Fan W.","year":"2010","unstructured":"W. Fan , J. Li , S. Ma , H. Wang , and Y. Wu . Graph Homomorphism Revisited for Graph Matching . PVLDB , 2010 . W. Fan, J. Li, S. Ma, H. Wang, and Y. Wu. Graph Homomorphism Revisited for Graph Matching. PVLDB, 2010."},{"key":"e_1_2_1_13_1","volume-title":"AAAI FS.","author":"Gallagher B.","year":"2006","unstructured":"B. Gallagher . Matching Structure and Semantics: A Survey on Graph-Based Pattern Matching . AAAI FS. , 2006 . B. Gallagher. Matching Structure and Semantics: A Survey on Graph-Based Pattern Matching. AAAI FS., 2006."},{"key":"e_1_2_1_14_1","volume-title":"ALT","author":"Han J.","year":"2009","unstructured":"J. Han . Mining Heterogeneous Information Networks by Exploring the Power of Links . ALT , 2009 . J. Han. Mining Heterogeneous Information Networks by Exploring the Power of Links. ALT, 2009."},{"key":"e_1_2_1_15_1","volume-title":"LNCS","author":"Han L.","year":"2011","unstructured":"L. Han , T. Finin , and A. Joshi . GoRelations: An Intuitive Query System for DBpedia . LNCS , 2011 . 10.1007\/978-3-642-29923-0_22 L. Han, T. Finin, and A. Joshi. GoRelations: An Intuitive Query System for DBpedia. LNCS, 2011. 10.1007\/978-3-642-29923-0_22"},{"key":"e_1_2_1_16_1","volume-title":"SIGMOD","author":"He H.","year":"2007","unstructured":"H. He , H. Wang , J. Yang , and P. S. Yu . BLINKS: Ranked Keyword Searches on Graphs . SIGMOD , 2007 . 10.1145\/1247480.1247516 H. He, H. Wang, J. Yang, and P. S. Yu. BLINKS: Ranked Keyword Searches on Graphs. SIGMOD, 2007. 10.1145\/1247480.1247516"},{"key":"e_1_2_1_17_1","volume-title":"WebDB","author":"Liu J.","year":"2006","unstructured":"J. Liu and X. Dong and A. Halevy . Answering Structured Queries on Unstructured Data . WebDB , 2006 . J. Liu and X. Dong and A. Halevy. Answering Structured Queries on Unstructured Data. WebDB, 2006."},{"key":"e_1_2_1_18_1","volume-title":"PVLDB","author":"Kargar M.","year":"2011","unstructured":"M. Kargar and A. An . Keyword Search in Graphs: Finding r-cliques . PVLDB , 2011 . M. Kargar and A. An. Keyword Search in Graphs: Finding r-cliques. PVLDB, 2011."},{"key":"e_1_2_1_19_1","volume-title":"Nucleic Acids Res","author":"Kelley B. P.","year":"2004","unstructured":"B. P. Kelley , B. Yuan , F. Lewitter , R. Sharan , B. R. Stockwell , and T. Ideker . PathBLAST: A Tool for Alignment of Protein Interaction Networks . Nucleic Acids Res , 2004 . B. P. Kelley, B. Yuan, F. Lewitter, R. Sharan, B. R. Stockwell, and T. Ideker. PathBLAST: A Tool for Alignment of Protein Interaction Networks. Nucleic Acids Res, 2004."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989418"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183684"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl287"},{"key":"e_1_2_1_23_1","volume-title":"PVLDB","author":"Ma S.","year":"2012","unstructured":"S. Ma , Y. Cao , W. Fan , J. Huai , and T. Wo . Capturing Topology in Graph Pattern Matching . PVLDB , 2012 . S. Ma, Y. Cao, W. Fan, J. Huai, and T. Wo. Capturing Topology in Graph Pattern Matching. PVLDB, 2012."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_25_1","volume-title":"ICDE","author":"Melnik S.","year":"2002","unstructured":"S. Melnik , H. G.- Molina , and E. Rahm . Similarity Flooding: A Versatile Graph Matching Algorithm and its Application to Schema Matching . ICDE , 2002 . S. Melnik, H. G.-Molina, and E. Rahm. Similarity Flooding: A Versatile Graph Matching Algorithm and its Application to Schema Matching. ICDE, 2002."},{"key":"e_1_2_1_26_1","author":"Mongiov\u00ec M.","year":"2010","unstructured":"M. Mongiov\u00ec , R. D. Natale , R. Giugno , A. Pulvirenti , A. Ferro , and R. Sharan . SIGMA: A Set-Cover-Based Inexact Graph Matching Algorithm. J. Bioinfo. and Comp. Bio. , 2010 . M. Mongiov\u00ec, R. D. Natale, R. Giugno, A. Pulvirenti, A. Ferro, and R. Sharan. SIGMA: A Set-Cover-Based Inexact Graph Matching Algorithm. J. Bioinfo. and Comp. Bio., 2010.","journal-title":"SIGMA: A Set-Cover-Based Inexact Graph Matching Algorithm. J. Bioinfo. and Comp. Bio."},{"key":"e_1_2_1_27_1","author":"Papadimitriou C.","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis . Optimization, Approximation, and Complexity Classes. J. Comp. and Sys. Sc. , 1991 . C. Papadimitriou and M. Yannakakis. Optimization, Approximation, and Complexity Classes. J. Comp. and Sys. Sc., 1991.","journal-title":"Optimization, Approximation, and Complexity Classes. J. Comp. and Sys. Sc."},{"key":"e_1_2_1_28_1","volume-title":"SIGMOD","author":"Papakonstantinou Y.","year":"1999","unstructured":"Y. Papakonstantinou and V. Vassalos . Query Rewriting for Semistructured Data . SIGMOD , 1999 . 10.1145\/304182.304222 Y. Papakonstantinou and V. Vassalos. Query Rewriting for Semistructured Data. SIGMOD, 1999. 10.1145\/304182.304222"},{"key":"e_1_2_1_29_1","volume-title":"American Association of AI Conf.","author":"Pearl J.","year":"1982","unstructured":"J. Pearl . Reverend Bayes on inference engines: A distributed Hierarchical Approach . American Association of AI Conf. , 1982 . J. Pearl. Reverend Bayes on inference engines: A distributed Hierarchical Approach. American Association of AI Conf., 1982."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.inffus.2009.12.001"},{"key":"e_1_2_1_31_1","volume-title":"AI Magazine","author":"Sen P.","year":"2008","unstructured":"P. Sen , G. M. Namata , M. Bilgic , L. Getoor , B. Gallagher , and T. Eliassi-Rad . Collective Classification in Network Data . AI Magazine , 2008 . P. Sen, G. M. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad. Collective Classification in Network Data. AI Magazine, 2008."},{"key":"e_1_2_1_32_1","volume-title":"PVLDB","author":"Shang H.","year":"2008","unstructured":"H. Shang , Y. Zhang , X. Lin , and J. Yu . Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism . PVLDB , 2008 . H. Shang, Y. Zhang, X. Lin, and J. Yu. Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism. PVLDB, 2008."},{"key":"e_1_2_1_33_1","volume-title":"PNAS","author":"Singh R.","year":"2008","unstructured":"R. Singh , J. Xu , and B. Berger . Global Alignment of Multiple Protein Interaction Networks with Application to Functional Orthology Detection . PNAS , 2008 . R. Singh, J. Xu, and B. Berger. Global Alignment of Multiple Protein Interaction Networks with Application to Functional Orthology Detection. PNAS, 2008."},{"key":"e_1_2_1_34_1","volume-title":"PVLDB","author":"Sun Z.","year":"2012","unstructured":"Z. Sun , H. Wang , H. Wang , B. Shao , and J. Li . Efficient Subgraph Matching on Billion Node Graphs . PVLDB , 2012 . Z. Sun, H. Wang, H. Wang, B. Shao, and J. Li. Efficient Subgraph Matching on Billion Node Graphs. PVLDB, 2012."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl571"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497505"},{"key":"e_1_2_1_37_1","volume-title":"KDD","author":"Tong H.","year":"2007","unstructured":"H. Tong , C. Faloutsos , B. Gallagher , and T. Eliassi-Rad . Fast Best-Effort Pattern Matching in Large Attributed Graphs . KDD , 2007 . 10.1145\/1281192.1281271 H. Tong, C. Faloutsos, B. Gallagher, and T. Eliassi-Rad. Fast Best-Effort Pattern Matching in Large Attributed Graphs. KDD, 2007. 10.1145\/1281192.1281271"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.76"},{"key":"e_1_2_1_40_1","volume-title":"Filtering for Subgraph Isomorphism. CP","author":"Zampelli S.","year":"2007","unstructured":"S. Zampelli , Y. Deville , C. Solnon , S. Sorlin , and P. Dupont . Filtering for Subgraph Isomorphism. CP , 2007 . S. Zampelli, Y. Deville, C. Solnon, S. Sorlin, and P. Dupont. Filtering for Subgraph Isomorphism. CP, 2007."},{"key":"e_1_2_1_41_1","volume-title":"PVLDB","author":"Zhang S.","year":"2010","unstructured":"S. Zhang , J. Yang , and W. Jin . SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs . PVLDB , 2010 . S. Zhang, J. Yang, and W. Jin. SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs. PVLDB, 2010."},{"key":"e_1_2_1_42_1","volume-title":"SIGMOD","author":"Zhong Q.","year":"2009","unstructured":"Q. Zhong , H. Li , J. Li , G. Xie , J. Tang , L. Zhou , and Y. Pan . A Gauss Function Based Approach for Unbalanced Ontology Matching . SIGMOD , 2009 . 10.1145\/1559845.1559915 Q. Zhong, H. Li, J. Li, G. Xie, J. Tang, L. Zhou, and Y. Pan. A Gauss Function Based Approach for Unbalanced Ontology Matching. SIGMOD, 2009. 10.1145\/1559845.1559915"},{"key":"e_1_2_1_43_1","volume-title":"VLDB","author":"Zou L.","year":"2011","unstructured":"L. Zou , J. Mo , L. Chen , M. T. \u00d6zsu , and D. Zhao . gStore: Answering SPARQL Queries via Subgraph Matching . VLDB , 2011 . L. Zou, J. Mo, L. Chen, M. T. \u00d6zsu, and D. Zhao. gStore: Answering SPARQL Queries via Subgraph Matching. VLDB, 2011."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2535569.2448952","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T06:04:47Z","timestamp":1672207487000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2535569.2448952"}},"subtitle":["fast graph search with label similarity"],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.14778\/2535569.2448952"],"URL":"https:\/\/doi.org\/10.14778\/2535569.2448952","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}