{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T06:49:47Z","timestamp":1769842187854,"version":"3.49.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>Recent interest in graph pattern mining has shifted from finding all frequent subgraphs to obtaining a small subset of frequent subgraphs that are representative, discriminative or significant. The main motivation behind that is to cope with the scalability problem that the graph mining algorithms suffer when mining databases of large graphs. Another motivation is to obtain a succinct output set that is informative and useful. In the same spirit, researchers also proposed sampling based algorithms that sample the output space of the frequent patterns to obtain representative subgraphs. In this work, we propose a generic sampling framework that is based on Metropolis-Hastings algorithm to sample the output space of frequent subgraphs. Our experiments on various sampling strategies show the versatility, utility and efficiency of the proposed sampling approach.<\/jats:p>","DOI":"10.14778\/1687627.1687710","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"730-741","source":"Crossref","is-referenced-by-count":91,"title":["Output space sampling for graph patterns"],"prefix":"10.14778","volume":"2","author":[{"given":"Mohammad","family":"Al Hasan","sequence":"first","affiliation":[{"name":"Rensselaer Polytechnic Institute, Troy, NY"}]},{"given":"Mohammed J.","family":"Zaki","sequence":"additional","affiliation":[{"name":"Rensselaer Polytechnic Institute, Troy, NY"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Cell-graph mining for breast tissue modeling and analysis","author":"Bilgin C.","year":"2007","unstructured":"C. Bilgin , C. Demir , C. Nagi , and B. Yener . Cell-graph mining for breast tissue modeling and analysis . In IEEE Engineering in Medicine and Biology Society , 2007 . C. Bilgin, C. Demir, C. Nagi, and B. Yener. Cell-graph mining for breast tissue modeling and analysis. In IEEE Engineering in Medicine and Biology Society, 2007."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.85"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.109"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2089856.2089868"},{"key":"e_1_2_1_5_1","volume-title":"In Proc. of Neural Information Processing Systems (NIPS)","author":"Chu C.","year":"2006","unstructured":"C. Chu , S. Kim , Y. Lin , Y. Yu , G. Bradski , A. Ng , and K. Olukotun . Map-reduce for machine learning on multicore . In In Proc. of Neural Information Processing Systems (NIPS) , 2006 . C. Chu, S. Kim, Y. Lin, Y. Yu, G. Bradski, A. Ng, and K. Olukotun. Map-reduce for machine learning on multicore. In In Proc. of Neural Information Processing Systems (NIPS), 2006."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514927"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/sam.v1:2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-008-0098-x"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775114"},{"key":"e_1_2_1_10_1","volume-title":"Spectral Graph Theory","author":"Chung R. K.","year":"1997","unstructured":"R. K. Chung . Spectral Graph Theory . Americal Mathematical Society , 1997 . R. K. Chung. Spectral Graph Theory. Americal Mathematical Society, 1997."},{"key":"e_1_2_1_11_1","volume-title":"MIT Laboratory of Computer Science","author":"Guruswami V.","year":"2000","unstructured":"V. Guruswami . Rapidly mixing markov chains: A comparison of techniques. Technical report , MIT Laboratory of Computer Science , 2000 . V. Guruswami. Rapidly mixing markov chains: A comparison of techniques. Technical report, MIT Laboratory of Computer Science, 2000."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972795.56"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/974614.974655"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/951949.952101"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014123"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.124"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401941"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502533"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/645496.658027"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401949"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335226"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/211390"},{"key":"e_1_2_1_23_1","series-title":"SIAM Int'l Conf. on Data Mining","volume-title":"Near-optimal supervised feature selection among frequent subgraphs","author":"Thoma M.","year":"2009","unstructured":"M. Thoma , H. Cheng , A. Gretton , J. Han , H. Kriegel , A. Smola , L. Song , P. Yu , X. Yan , and K. Borgwardt . Near-optimal supervised feature selection among frequent subgraphs . In SIAM Int'l Conf. on Data Mining , 2009 . M. Thoma, H. Cheng, A. Gretton, J. Han, H. Kriegel, A. Smola, L. Song, P. Yu, X. Yan, and K. Borgwardt. Near-optimal supervised feature selection among frequent subgraphs. In SIAM Int'l Conf. on Data Mining, 2009."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014134"},{"key":"e_1_2_1_25_1","volume-title":"Simulation and the Monte Carlo Method","author":"Rubinstein R. Y.","year":"2008","unstructured":"R. Y. Rubinstein and D. K. Kroese . Simulation and the Monte Carlo Method , 2 nd Ed. John Wiley & Sons , 2008 . R. Y. Rubinstein and D. K. Kroese. Simulation and the Monte Carlo Method, 2nd Ed. John Wiley & Sons, 2008.","edition":"2"},{"key":"e_1_2_1_26_1","volume-title":"BirkHauser","author":"Sinclair A.","year":"1992","unstructured":"A. Sinclair . Algorithms for Random Generation and Counting . BirkHauser , 1992 . A. Sinclair. Algorithms for Random Generation and Counting. BirkHauser, 1992."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775053"},{"key":"e_1_2_1_28_1","first-page":"134","volume-title":"Sampling Large Databases for Association Rules. In VLDB Proceedings","author":"Toivonen H.","year":"1996","unstructured":"H. Toivonen . Sampling Large Databases for Association Rules. In VLDB Proceedings , pages 134 -- 145 , 1996 . H. Toivonen. Sampling Large Databases for Association Rules. In VLDB Proceedings, pages 134--145, 1996."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_30_1","volume-title":"In Proc. of Neural Information Processing Systems (NIPS)","author":"Vishwanathan S.","year":"2006","unstructured":"S. Vishwanathan , K. Borgwardt , and N. Schraudolph . Fast computation of graph kernels . In In Proc. of Neural Information Processing Systems (NIPS) , 2006 . S. Vishwanathan, K. Borgwardt, and N. Schraudolph. Fast computation of graph kernels. In In Proc. of Neural Information Processing Systems (NIPS), 2006."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150495"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083675"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081907"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376662"},{"key":"e_1_2_1_35_1","volume-title":"ICDM","author":"Yan X.","year":"2002","unstructured":"X. Yan and J. Han . gSpan: Graph-Based Substructure Pattern Mining . In ICDM , 2002 . X. Yan and J. Han. gSpan: Graph-Based Substructure Pattern Mining. In ICDM, 2002."},{"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.1007\/s10115-007-0081-7"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687710","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:31:32Z","timestamp":1672227092000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687710"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687710"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687710","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}