{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T03:42:09Z","timestamp":1784950929544,"version":"3.55.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,3]]},"abstract":"<jats:p>\n            Mining frequent subgraphs is an important operation on graphs; it is defined as finding all subgraphs that appear frequently in a database according to a given frequency threshold. Most existing work assumes a database of many small graphs, but modern applications, such as social networks, citation graphs, or protein-protein interactions in bioinformatics, are modeled as a single large graph. In this paper we present GraMi, a novel framework for frequent subgraph mining in a single large graph. GraMi undertakes a novel approach that only finds the\n            <jats:italic>minimal<\/jats:italic>\n            set of instances to satisfy the frequency threshold and avoids the costly enumeration of\n            <jats:italic>all<\/jats:italic>\n            instances required by previous approaches. We accompany our approach with a heuristic and optimizations that significantly improve performance. Additionally, we present an extension of GraMi that mines frequent patterns. Compared to subgraphs, patterns offer a more powerful version of matching that captures transitive interactions between graph nodes (like friend of a friend) which are very common in modern applications. Finally, we present CGraMi, a version supporting structural and semantic constraints, and AGraMi, an approximate version producing results with no false positives. Our experiments on real data demonstrate that our framework is up to 2 orders of magnitude faster and discovers more interesting patterns than existing approaches.\n          <\/jats:p>","DOI":"10.14778\/2732286.2732289","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"517-528","source":"Crossref","is-referenced-by-count":239,"title":["GraMi"],"prefix":"10.14778","volume":"7","author":[{"given":"Mohammed","family":"Elseidy","sequence":"first","affiliation":[{"name":"Ecole Polytechnique F\u00e9d\u00e9rale de Lausanne"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ehab","family":"Abdelhamid","sequence":"additional","affiliation":[{"name":"King Abdullah University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Spiros","family":"Skiadopoulos","sequence":"additional","affiliation":[{"name":"University of Peloponnese"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Panos","family":"Kalnis","sequence":"additional","affiliation":[{"name":"King Abdullah University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,3]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1786574.1786663"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2007.36"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497500"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITB.2009.2028234"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2324796.2324831"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1618595.1618605"},{"key":"e_1_2_1_8_1","first-page":"22","volume-title":"Proc. of AAAI","author":"de Givry S.","year":"2006","unstructured":"S. de Givry , T. Schiex , and G. Verfaillie . Exploiting tree decomposition and soft local consistency in weighted CSP . In Proc. of AAAI , pages 22 -- 27 , 2006 . S. de Givry, T. Schiex, and G. Verfaillie. Exploiting tree decomposition and soft local consistency in weighted CSP. In Proc. of AAAI, pages 22--27, 2006."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/951949.952152"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304220"},{"key":"e_1_2_1_11_1","first-page":"1451","volume-title":"Proc. of IJCAI","author":"Domshlak C.","year":"2001","unstructured":"C. Domshlak , R. I. Brafman , and S. E. Shimony . Preference-based configuration of web page content . In Proc. of IJCAI , pages 1451 -- 1456 , 2001 . C. Domshlak, R. I. Brafman, and S. E. Shimony. Preference-based configuration of web page content. In Proc. of IJCAI, pages 1451--1456, 2001."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2007.105"},{"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 & Co. , 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1979."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/647859.736135"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/645496.658051"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807261"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645496.658027"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1032649.1033500"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-005-0003-9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448946"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(77)90007-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(79)90023-9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.133"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839491"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376662"},{"key":"e_1_2_1_29_1","first-page":"721","volume-title":"Proc. of ICDM","author":"Yan X.","year":"2002","unstructured":"X. Yan and J. Han . gSpan: Graph-based substructure pattern mining . In Proc. of ICDM , pages 721 -- 724 , 2002 . X. Yan and J. Han. gSpan: Graph-based substructure pattern mining. In Proc. of ICDM, pages 721--724, 2002."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956784"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_1_32_1","volume-title":"Social computing data repository at ASU","author":"Zafarani R.","year":"2009","unstructured":"R. Zafarani and H. Liu . Social computing data repository at ASU , 2009 . R. Zafarani and H. Liu. Social computing data repository at ASU, 2009."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764441.1764481"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687727"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732286.2732289","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:00:37Z","timestamp":1672225237000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732286.2732289"}},"subtitle":["frequent subgraph and pattern mining in a single large graph"],"short-title":[],"issued":{"date-parts":[[2014,3]]},"references-count":33,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["10.14778\/2732286.2732289"],"URL":"https:\/\/doi.org\/10.14778\/2732286.2732289","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,3]]}}}