{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T01:31:29Z","timestamp":1779327089949,"version":"3.51.4"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,4,16]],"date-time":"2018-04-16T00:00:00Z","timestamp":1523836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"funder":[{"name":"European Research Council","award":["Starting Grant DMAP 680153"],"award-info":[{"award-number":["Starting Grant DMAP 680153"]}]},{"name":"Sapienza Univ. Rome","award":["Inter-disciplinary research grant C26M15ALKP"],"award-info":[{"award-number":["Inter-disciplinary research grant C26M15ALKP"]}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"crossref","award":["Focused Research Award"],"award-info":[{"award-number":["Focused Research Award"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003407","name":"MIUR","doi-asserted-by":"crossref","award":["Grant RBSI14Q743"],"award-info":[{"award-number":["Grant RBSI14Q743"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2018,8,31]]},"abstract":"<jats:p>Counting graphlets is a well-studied problem in graph mining and social network analysis. Recently, several papers explored very simple and natural algorithms based on Monte Carlo sampling of Markov Chains (MC), and reported encouraging results. We show, perhaps surprisingly, that such algorithms are outperformed by color coding (CC)\u00a0[2], a sophisticated algorithmic technique that we extend to the case of graphlet sampling and for which we prove strong statistical guarantees. Our computational experiments on graphs with millions of nodes show CC to be more accurate than MC; furthermore, we formally show that the mixing time of the MC approach is too high in general, even when the input graph has high conductance. All this comes at a price however. While MC is very efficient in terms of space, CC\u2019s memory requirements become demanding when the size of the input graph and that of the graphlets grow. And yet, our experiments show that CC can push the limits of the state-of-the-art, both in terms of the size of the input graph and of that of the graphlets.<\/jats:p>","DOI":"10.1145\/3186586","type":"journal-article","created":{"date-parts":[[2018,4,18]],"date-time":"2018-04-18T17:21:50Z","timestamp":1524072110000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":42,"title":["Motif Counting Beyond Five Nodes"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5211-2264","authenticated-orcid":false,"given":"Marco","family":"Bressan","sequence":"first","affiliation":[{"name":"Sapienza University of Rome, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Flavio","family":"Chierichetti","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[{"name":"Google Research, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leucci","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,4,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018732"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 30th IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201916)","author":"Chakaravarthy V. T.","unstructured":"V. T. Chakaravarthy , M. Kapralov , P. Murali , F. Petrini , X. Que , Y. Sabharwal , and B. Schieber . 2016. Subgraph counting: Color coding beyond trees . In Proceedings of the 30th IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201916) . 2--11. V. T. Chakaravarthy, M. Kapralov, P. Murali, F. Petrini, X. Que, Y. Sabharwal, and B. Schieber. 2016. Subgraph counting: Color coding beyond trees. In Proceedings of the 30th IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201916). 2--11."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021940"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the Integrated Community Case Management (ICCM\u201907)","author":"Chung F.","year":"2007","unstructured":"F. Chung . 2007 . Four proofs for the Cheeger inequality and graph partition algorithms . In Proceedings of the Integrated Community Case Management (ICCM\u201907) . F. Chung. 2007. Four proofs for the Cheeger inequality and graph partition algorithms. In Proceedings of the Integrated Community Case Management (ICCM\u201907)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/140978211"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0029"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.11.015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487678"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367591"},{"key":"e_1_2_1_17_1","volume-title":"Wilmer","author":"Levin David A.","year":"2009","unstructured":"David A. Levin , Yuval Peres , and Elizabeth L . Wilmer . 2009 . Markov Chains and Mixing Times. American Mathematical Society . xviii+371 pages. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. 2009. Markov Chains and Mixing Times. American Mathematical Society. xviii+371 pages."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052597"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16112-9_2"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2013.30"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_2_1_22_1","volume-title":"Kwok Pui Choi, and Louxin Zhang","author":"Tran Ngoc Hieu","year":"2013","unstructured":"Ngoc Hieu Tran , Kwok Pui Choi, and Louxin Zhang . 2013 . Counting motifs in the human interactome. Nature Communications 4 (Aug. 2013), Article 2241. Ngoc Hieu Tran, Kwok Pui Choi, and Louxin Zhang. 2013. Counting motifs in the human interactome. Nature Communications 4 (Aug. 2013), Article 2241."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_2_1_24_1","volume-title":"Graph Theory","author":"Tutte W. T.","unstructured":"W. T. Tutte . 2001. Graph Theory . Cambridge University Press . https:\/\/books.google.it\/books?id&equals;uTGhooU37h4C. W. T. Tutte. 2001. Graph Theory. Cambridge University Press. https:\/\/books.google.it\/books?id&equals;uTGhooU37h4C."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592675"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.92917"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629564"},{"key":"e_1_2_1_28_1","unstructured":"Pinghui Wang Xiangliang Zhang Zhenguo Li Jiefeng Cheng John C. S. Lui Don Towsley Junzhou Zhao Jing Tao and Xiaohong Guan. 2016. A fast sampling method of exploring graphlet degrees of large directed and undirected graphs. arXiv:1604.08691  Pinghui Wang Xiangliang Zhang Zhenguo Li Jiefeng Cheng John C. S. Lui Don Towsley Junzhou Zhao Jing Tao and Xiaohong Guan. 2016. A fast sampling method of exploring graphlet degrees of large directed and undirected graphs. arXiv:1604.08691"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2756836"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076619X"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.67"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186586","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3186586","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:28Z","timestamp":1750212688000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186586"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,16]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3186586"],"URL":"https:\/\/doi.org\/10.1145\/3186586","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,16]]},"assertion":[{"value":"2017-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}