{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T12:21:54Z","timestamp":1762431714322},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,7]]},"abstract":"<jats:p>The randomized technique of color coding is behind state-of-the-art algorithms for estimating graph motif counts. Those algorithms, however, are not yet capable of scaling well to very large graphs with billions of edges. In this paper we develop novel tools for the \"motif counting via color coding\" framework. As a result, our new algorithm, MOTIYO, scales to much larger graphs while at the same time providing more accurate motif counts than ever before. This is achieved thanks to two types of improvements. First, we design new succinct data structures for fast color coding operations, and a biased coloring trick that trades accuracy versus resource usage. These optimizations drastically reduce the resource requirements of color coding. Second, we develop an adaptive motif sampling strategy, based on a fractional set cover problem, that breaks the additive approximation barrier of standard sampling. This gives multiplicative approximations for all motifs at once, allowing us to count not only the most frequent motifs but also extremely rare ones.<\/jats:p>\n          <jats:p>To give an idea of the improvements, in 40 minutes MOTIVO counts 7-nodes motifs on a graph with 65M nodes and 1.8B edges; this is 30 and 500 times larger than the state of the art, respectively in terms of nodes and edges. On the accuracy side, in one hour MOTIVO produces accurate counts of \u2248 10.000 distinct 8-node motifs on graphs where state-of-the-art algorithms fail even to find the second most frequent motif. Our method requires just a high-end desktop machine. These results show how color coding can bring motif mining to the realm of truly massive graphs using only ordinary hardware.<\/jats:p>","DOI":"10.14778\/3342263.3342640","type":"journal-article","created":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T18:36:11Z","timestamp":1568831771000},"page":"1651-1663","source":"Crossref","is-referenced-by-count":40,"title":["Motivo"],"prefix":"10.14778","volume":"12","author":[{"given":"Marco","family":"Bressan","sequence":"first","affiliation":[{"name":"Sapienza Universit\u00e0 di Roma"}]},{"given":"Stefano","family":"Leucci","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[{"name":"Sapienza Universit\u00e0 di Roma"}]}],"member":"320","published-online":{"date-parts":[[2019,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.3389\/fbioe.2015.00157"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1214\/09-AAP656"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3162016"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_2_1_7_1","volume-title":"Proc. of IPEC","author":"Bressan M.","year":"2019","unstructured":"M. Bressan . Counting subgraphs via DAG tree decompositions . In Proc. of IPEC , 2019 . (To appear). M. Bressan. Counting subgraphs via DAG tree decompositions. In Proc. of IPEC, 2019. (To appear)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018732"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186586"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.122"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021940"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"Dubhashi D.","year":"2009","unstructured":"D. Dubhashi and A. Panconesi . Concentration of Measure for the Analysis of Randomized Algorithms . Cambridge University Press , New York, NY, USA , 1 st edition, 2009 . D. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1st edition, 2009.","edition":"1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996452"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0029"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052636"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969046"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052597"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2013.30"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3059194"},{"key":"e_1_2_1_23_1","volume-title":"Counting motifs in the human interactome. Nature Communications, 4(2241)","author":"Tran N. H.","year":"2013","unstructured":"N. H. Tran , K. P. Choi , and L. Zhang . Counting motifs in the human interactome. Nature Communications, 4(2241) , 2013 . N. H. Tran, K. P. Choi, and L. Zhang. Counting motifs in the human interactome. Nature Communications, 4(2241), 2013."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.92917"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629564"},{"key":"e_1_2_1_26_1","volume-title":"Moss: A scalable tool for efficiently sampling and counting 4-and 5-node graphlets. CoRR, abs\/1509.08089","author":"Wang P.","year":"2015","unstructured":"P. Wang , J. Tao , J. Zhao , and X. Guan . Moss: A scalable tool for efficiently sampling and counting 4-and 5-node graphlets. CoRR, abs\/1509.08089 , 2015 . P. Wang, J. Tao, J. Zhao, and X. Guan. Moss: A scalable tool for efficiently sampling and counting 4-and 5-node graphlets. CoRR, abs\/1509.08089, 2015."},{"key":"e_1_2_1_27_1","volume-title":"A fast sampling method of exploring graphlet degrees of large directed and undirected graphs. CoRR, abs\/1604.08691","author":"Wang P.","year":"2016","unstructured":"P. Wang , X. Zhang , Z. Li , J. Cheng , J. C. S. Lui , D. Towsley , J. Zhao , J. Tao , and X. Guan . A fast sampling method of exploring graphlet degrees of large directed and undirected graphs. CoRR, abs\/1604.08691 , 2016 . P. Wang, X. Zhang, Z. Li, J. Cheng, J. C. S. Lui, D. Towsley, J. Zhao, J. Tao, and X. Guan. A fast sampling method of exploring graphlet degrees of large directed and undirected graphs. CoRR, abs\/1604.08691, 2016."},{"issue":"4547","key":"e_1_2_1_28_1","first-page":"04","article-title":"Revealing the hidden language of complex networks","volume":"4","author":"Yavero\u011flu N.","year":"2014","unstructured":"\u00d6. N. Yavero\u011flu , N. Malod-Dognin , D. Davis , Z. Levnajic , V. Janjic , R. Karapandza , A. Stojmirovic , and N. Pr\u017eulj . Revealing the hidden language of complex networks . Scientific Reports , 4 : 4547 EP -, 04 2014 . \u00d6. N. Yavero\u011flu, N. Malod-Dognin, D. Davis, Z. Levnajic, V. Janjic, R. Karapandza, A. Stojmirovic, and N. Pr\u017eulj. Revealing the hidden language of complex networks. Scientific Reports, 4:4547 EP -, 04 2014.","journal-title":"Scientific Reports"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.67"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3342263.3342640","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:54:50Z","timestamp":1672221290000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3342263.3342640"}},"subtitle":["fast motif counting via succinct color coding and adaptive sampling"],"short-title":[],"issued":{"date-parts":[[2019,7]]},"references-count":30,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["10.14778\/3342263.3342640"],"URL":"https:\/\/doi.org\/10.14778\/3342263.3342640","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,7]]}}}