{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:27Z","timestamp":1750220427351,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T00:00:00Z","timestamp":1621382400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,6,28]]},"abstract":"<jats:p>\n            We address the problem of computing the distribution of induced connected subgraphs, aka\n            <jats:italic>graphlets<\/jats:italic>\n            or\n            <jats:italic>motifs<\/jats:italic>\n            , in large graphs. The current state-of-the-art algorithms estimate the motif counts via uniform sampling by leveraging the color coding technique by Alon, Yuster, and Zwick. In this work, we extend the applicability of this approach by introducing a set of algorithmic optimizations and techniques that reduce the running time and space usage of color coding and improve the accuracy of the counts. To this end, we first show how to optimize color coding to efficiently build a compact table of a representative subsample of all graphlets in the input graph. For 8-node motifs, we can build such a table in one hour for a graph with 65M nodes and 1.8B edges, which is\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            times larger than the state of the art. We then introduce a novel adaptive sampling scheme that breaks the \u201cadditive error barrier\u201d of uniform sampling, guaranteeing multiplicative approximations instead of just additive ones. This allows us to count not only the most frequent motifs, but also extremely rare ones. For instance, on one graph we accurately count nearly 10.000 distinct 8-node motifs whose relative frequency is so small that uniform sampling would literally take centuries to find them. Our results show that color coding is still the most promising approach to scalable motif counting.\n          <\/jats:p>","DOI":"10.1145\/3447397","type":"journal-article","created":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T17:08:53Z","timestamp":1621444133000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Faster Motif Counting via Succinct Color Coding and Adaptive Sampling"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5211-2264","authenticated-orcid":false,"given":"Marco","family":"Bressan","sequence":"first","affiliation":[{"name":"Universit\u00e0 Statale di Milano, Italy"}]},{"given":"Stefano","family":"Leucci","sequence":"additional","affiliation":[{"name":"Universit\u00e0 dell\u2019Aquila, Italy"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[{"name":"Sapienza Universit\u00e0 di Roma, Roma, Italy"}]}],"member":"320","published-online":{"date-parts":[[2021,5,19]]},"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.1016\/j.ipl.2019.105851"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/09-AAP656"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3162016"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018732"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186586"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342640"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.122"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389137"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021940"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319875"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1568639"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2794080"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0029"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118777.3119179"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052636"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371839"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1038\/35075138"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359633"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969046"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330995"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052597"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.133"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2013.30"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_2_1_34_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. Nat Commun 4, 2241 (2013). Ngoc Hieu Tran, Kwok Pui Choi, and Louxin Zhang. 2013. Counting motifs in the human interactome. Nat Commun 4, 2241 (2013)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.92917"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629564"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2756836"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-018-1301-z"},{"key":"e_1_2_1_39_1","volume-title":"Article 4547","author":"Yavero\u011flu \u00d6mer Nebil","year":"2014","unstructured":"\u00d6mer Nebil Yavero\u011flu , No\u00ebl Malod-Dognin , Darren Davis , Zoran Levnajic , Vuk Janjic , Rasa Karapandza , Aleksandar Stojmirovic , and Nata\u0161a Pr\u017eulj . 2014. Revealing the hidden language of complex networks. Sci Rep 4 , Article 4547 ( 2014 ). DOI:http:\/\/dx.doi.org\/10.1038\/srep04547 10.1038\/srep04547 \u00d6mer Nebil Yavero\u011flu, No\u00ebl Malod-Dognin, Darren Davis, Zoran Levnajic, Vuk Janjic, Rasa Karapandza, Aleksandar Stojmirovic, and Nata\u0161a Pr\u017eulj. 2014. Revealing the hidden language of complex networks. Sci Rep 4, Article 4547 (2014). DOI:http:\/\/dx.doi.org\/10.1038\/srep04547"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0306752101"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407840"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.67"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.44"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447397","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447397","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:46:56Z","timestamp":1750193216000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447397"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,19]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6,28]]}},"alternative-id":["10.1145\/3447397"],"URL":"https:\/\/doi.org\/10.1145\/3447397","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2021,5,19]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}