{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:06:44Z","timestamp":1779131204242,"version":"3.51.4"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Hong Kong Research Grants Council","award":["17201823"],"award-info":[{"award-number":["17201823"]}]},{"name":"Hong Kong Research Grants Council","award":["17203122"],"award-info":[{"award-number":["17203122"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>\n                    In recent years, the problem of computing the frequencies of the induced\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -vertex subgraphs of a graph, or\n                    <jats:italic toggle=\"yes\">k-graphlets,<\/jats:italic>\n                    has become central. One approach for this problem is to sample\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -graphlets randomly. Classic algorithms for\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -graphlet sampling require loading the entire graph into main memory, making them impractical for massive graphs. To bypass this limitation, Bourreau et al. (NeurIPS 2024) introduced a\n                    <jats:italic toggle=\"yes\">streaming<\/jats:italic>\n                    algorithm that through nontrivial techniques makes only\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) passes using\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) memory. In this work we break their\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    )-pass bound by giving an algorithm that, for any fixed\n                    <jats:italic toggle=\"yes\">c<\/jats:italic>\n                    &gt; 0, makes\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (1\/\n                    <jats:italic toggle=\"yes\">c<\/jats:italic>\n                    ) passes using \u00d5(\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <jats:sup>\n                      1+\n                      <jats:italic toggle=\"yes\">c<\/jats:italic>\n                    <\/jats:sup>\n                    ) memory. As a consequence of their lower bound, our algorithm is optimal up to a factor of \u00d5 (n\n                    <jats:sup>c<\/jats:sup>\n                    ) in the memory usage. We use this sampling algorithm to obtain an efficient method of approximating\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -graphlet distributions. Experiments on real-world and synthetic graphs show that our algorithm is always at least as good as the one of Bourreau et al., and outperforms it by orders of magnitude on mildly dense graphs.\n                  <\/jats:p>","DOI":"10.1145\/3802010","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["An Efficient Streaming Algorithm for Approximating Graphlet Distributions"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5211-2264","authenticated-orcid":false,"given":"Marco","family":"Bressan","sequence":"first","affiliation":[{"name":"University of Milan, Milan, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8340-235X","authenticated-orcid":false,"given":"T-H. Hubert","family":"Chan","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-2396-8312","authenticated-orcid":false,"given":"Qipeng","family":"Kuang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2031-3974","authenticated-orcid":false,"given":"Mauro","family":"Sozio","sequence":"additional","affiliation":[{"name":"LUISS University, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2019.105851"},{"key":"e_1_2_1_2_1","first-page":"1446","article-title":"Graph sample and hold: a framework for big-graph analytics","author":"Ahmed Nesreen K.","year":"2014","unstructured":"Nesreen K. Ahmed, Nick G. Duffield, Jennifer Neville, and Ramana Rao Kompella. 2014. Graph sample and hold: a framework for big-graph analytics. In KDD. ACM, 1446-1455.","journal-title":"KDD. ACM"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_2_1_4_1","first-page":"623","article-title":"Reductions in streaming algorithms, with an application to counting triangles in graphs","author":"Bar-Yossef Ziv","year":"2002","unstructured":"Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs. In SODA. ACM\/SIAM, 623-632.","journal-title":"SODA. ACM\/SIAM"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3520240"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Yann Bourreau Marco Bressan T.-H. Hubert Chan Qipeng Kuang and Mauro Sozio. 2024. Efficient Streaming Algorithms for Graphlet Sampling. In NeurIPS.","DOI":"10.52202\/079017-0634"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451042"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Marco Bressan. 2021b. Efficient and near-optimal algorithms for sampling connected subgraphs. arXiv:2007.12102 [cs.DS]","DOI":"10.1145\/3406325.3451042"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00811-0"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3596495"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018732"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186586"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342640"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447397"},{"key":"e_1_2_1_17_1","volume-title":"Measuring User Influence in Twitter: The Million Follower Fallacy","author":"Cha Meeyoung","unstructured":"Meeyoung Cha, Hamed Haddadi, Fabr\u00edcio Benevenuto, and P. Krishna Gummadi. 2010. Measuring User Influence in Twitter: The Million Follower Fallacy. In ICWSM. The AAAI Press."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021940"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_2_1_22_1","volume-title":"ICML (Proceedings of Machine Learning Research","volume":"2210","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovic. 2019. Improved Parallel Algorithms for Density-Based Network Clustering. In ICML (Proceedings of Machine Learning Research, Vol. 97). PMLR, 2201-2210."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3192506"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0029"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1952.10483446"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.11.015"},{"key":"e_1_2_1_27_1","article-title":"A Space-Efficient Streaming Algorithm for Estimating Transitivity and Triangle Counts Using the Birthday Paradox","volume":"9","author":"Jha Madhav","year":"2015","unstructured":"Madhav Jha, C. Seshadhri, and Ali Pinar. 2015. A Space-Efficient Streaming Algorithm for Estimating Transitivity and Triangle Counts Using the Birthday Paradox. ACM Trans. Knowl. Discov. Data, Vol. 9, 3 (2015), 15:1-15:21.","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"e_1_2_1_28_1","first-page":"598","article-title":"Counting Arbitrary Subgraphs in Data Streams. In ICALP (2) (Lecture Notes in Computer Science, Vol. 7392)","author":"Kane Daniel M.","year":"2012","unstructured":"Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. 2012. Counting Arbitrary Subgraphs in Data Streams. In ICALP (2) (Lecture Notes in Computer Science, Vol. 7392). Springer, 598-609.","journal-title":"Springer"},{"key":"e_1_2_1_29_1","volume-title":"International World Wide Web Conferences Steering Committee \/ ACM, 1343-1350","author":"Kunegis J\u00e9r\u00f4me","year":"2013","unstructured":"J\u00e9r\u00f4me Kunegis. 2013. KONECT: the Koblenz network collection. In WWW (Companion Volume). International World Wide Web Conferences Steering Committee \/ ACM, 1343-1350."},{"key":"e_1_2_1_30_1","first-page":"591","article-title":"What is Twitter, a social network or a news media?","author":"Kwak Haewoon","year":"2010","unstructured":"Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue B. Moon. 2010. What is Twitter, a social network or a news media?. In WWW. ACM, 591-600.","journal-title":"WWW. ACM"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3022186"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976236.64"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330995"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5987"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16112-9_2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_2_1_40_1","volume-title":"Borgwardt","author":"Shervashidze Nino","year":"2009","unstructured":"Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt. 2009. Efficient graphlet kernels for large graph comparison. In AISTATS (JMLR Proceedings, Vol. 5). JMLR.org, 488-495."},{"key":"e_1_2_1_41_1","first-page":"43","article-title":"Triest: Counting local and global triangles in fully dynamic streams with fixed memory size","volume":"11","author":"Stefani Lorenzo De","year":"2017","unstructured":"Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, and Eli Upfal. 2017a. Triest: Counting local and global triangles in fully dynamic streams with fixed memory size. ACM TKDD, Vol. 11, 4 (2017), 43.","journal-title":"ACM TKDD"},{"key":"e_1_2_1_42_1","first-page":"776","article-title":"Tiered sampling: An efficient method for approximate counting sparse motifs in massive graph streams. In IEEE BigData","author":"Stefani Lorenzo De","year":"2017","unstructured":"Lorenzo De Stefani, Erisa Terolli, and Eli Upfal. 2017b. Tiered sampling: An efficient method for approximate counting sparse motifs in massive graph streams. In IEEE BigData. IEEE Computer Society, 776-786.","journal-title":"IEEE Computer Society"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341161.3342908"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629564"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802010","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:28:13Z","timestamp":1779128893000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802010"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802010"],"URL":"https:\/\/doi.org\/10.1145\/3802010","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}