{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T17:38:04Z","timestamp":1755797884498,"version":"3.44.0"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"<jats:p>\n            We study the problem of approximately counting\n            <jats:italic toggle=\"yes\">cliques<\/jats:italic>\n            and\n            <jats:italic toggle=\"yes\">near-cliques<\/jats:italic>\n            in a graph, where the access to the graph is only available through crawling its vertices. This model has been introduced recently to capture real-life scenarios in which the entire graph is too massive to be stored as a whole or be scanned entirely. Sampling vertices independently is non-trivial in this model, thus algorithms which rely on sampling often use a random walk. The goal is to provide an accurate estimate by seeing only a small portion of the graph. This model is known as the\n            <jats:italic toggle=\"yes\">random walk<\/jats:italic>\n            model or the\n            <jats:italic toggle=\"yes\">neighborhood query<\/jats:italic>\n            model.\n          <\/jats:p>\n          <jats:p>\n            We introduce\n            <jats:sc>DeMEtRIS<\/jats:sc>\n            : Dense Motif Estimation through Random Incident Sampling. This method provides a scalable algorithm for clique and near-clique counting in the random walk model. We prove the correctness of our algorithm through rigorous mathematical analysis and extensive experiments. Both our theoretical results and our experiments show that\n            <jats:sc>DeMEtRIS<\/jats:sc>\n            obtains a high precision estimation by only crawling a sub-linear portion on vertices. Therefore, we demonstrate a significant improvement over previous known results.\n          <\/jats:p>","DOI":"10.1145\/3699517","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:11:45Z","timestamp":1728303105000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["DeMEtRIS: Counting (near)-Cliques by Crawling"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5699-2948","authenticated-orcid":false,"given":"Suman","family":"Bera","sequence":"first","affiliation":[{"name":"Apple, San Jose, CA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6246-4615","authenticated-orcid":false,"given":"Jayesh","family":"Choudhari","sequence":"additional","affiliation":[{"name":"Cube Global Ltd., London, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7702-8250","authenticated-orcid":false,"given":"Shahrzad","family":"Haddadan","sequence":"additional","affiliation":[{"name":"Rutgers Business School, Piscataway, NJ, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7060-6775","authenticated-orcid":false,"given":"Sara","family":"Ahmadian","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,8,18]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Meta for Developers. Facebook User Public API. v12.0. Release date: September 14 2021. Retrieved January 2022 from https:\/\/developers.facebook.com\/docs\/graph-api\/reference\/user\/"},{"key":"e_1_3_1_3_2","unstructured":"Twitter Public API. v.1.1. Release date: 2012. Retrieved January 2022 from https:\/\/developer.twitter.com\/en\/docs\/twitter-api\/v1\/accounts-and-users\/follow-search-get-users\/overview"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl039"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2019.105851"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0287-3"},{"key":"e_1_3_1_7_2","article-title":"A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi, Mikhail Kapralov, and Sanjeev Khanna. 2019. A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling. In Proceedings of the 10th Innovations in Theoretical Computer Science (ITCS \u201919).","journal-title":"Proceedings of the 10th Innovations in Theoretical Computer Science (ITCS \u201919)"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839494"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3488560.3498383"},{"key":"e_1_3_1_10_2","first-page":"1702","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201918)","author":"Ben-Hamou Anna","year":"2018","unstructured":"Anna Ben-Hamou, Roberto I. Oliveira, and Yuval Peres. 2018. Estimating graph parameters via random walks with restarts. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201918). Society for Industrial and Applied Mathematics, 1702\u20131714."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20539"},{"key":"e_1_3_1_12_2","article-title":"Towards tighter space bounds for counting triangles and other substructures in graph streams","author":"Bera Suman K.","year":"2017","unstructured":"Suman K. Bera and Amit Chakrabarti. 2017. Towards tighter space bounds for counting triangles and other substructures in graph streams. In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science.","journal-title":"Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science"},{"key":"e_1_3_1_13_2","first-page":"312","volume-title":"Proceedings of the 16th ACM International Conference on Web Search and Data Mining","author":"Bera Suman K.","year":"2023","unstructured":"Suman K. Bera, Jayesh Choudhari, Shahrzad Haddadan, and Sara Ahmadian. 2023. DeMEtRIS: Counting (near)-cliques by crawling. In Proceedings of the 16th ACM International Conference on Web Search and Data Mining, 312\u2013320."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387665"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403073"},{"key":"e_1_3_1_16_2","first-page":"91","volume-title":"Proceedings of the IEEE 12th International Conference on Data Mining","author":"Bhuiyan Mansurul A.","year":"2012","unstructured":"Mansurul A. Bhuiyan, Mahmudur Rahman, Mahmuda Rahman, and Mohammad Al Hasan. 2012. Guise: Uniform sampling of graphlets for large graph analysis. In Proceedings of the IEEE 12th International Conference on Data Mining. IEEE, 91\u2013100."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451042"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00811-0"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342640"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00036"},{"key":"e_1_3_1_21_2","first-page":"253","volume-title":"Proceedings of the VLDB Endowment","volume":"10","author":"Chen Xiaowei","year":"2016","unstructured":"Xiaowei Chen, Yongkun Li, Pinghui Wang, and John C. S. Lui. 2016. A general framework for estimating graphlet statistics via random walk. Proceedings of the VLDB Endowment 10, 3 (2016), 253\u2013264."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883045"},{"key":"e_1_3_1_23_2","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP \u201918)","author":"Chierichetti Flavio","year":"2018","unstructured":"Flavio Chierichetti and Shahrzad Haddadan. 2018. On the complexity of sampling vertices uniformly from a graph. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP \u201918). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1086\/228943"},{"key":"e_1_3_1_25_2","unstructured":"Cyrus Cousins Shahrzad Haddadan and Eli Upfal. 2020. Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE. arXiv:2011.11129."},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568019"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186111"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054389"},{"key":"e_1_3_1_30_2","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP \u201917)","author":"Eden Talya","year":"2017","unstructured":"Talya Eden, Dana Ron, and C. Seshadhri. 2017. Sublinear time estimation of degree distribution moments: The degeneracy connection. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP \u201917). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188810"},{"key":"e_1_3_1_32_2","first-page":"1467","volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201920)","author":"Eden Talya","year":"2020","unstructured":"Talya Eden, Dana Ron, and C. Seshadhri. 2020. Faster sublinear approximation of the number of k-cliques in low-arboricity graphs. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201920). Society for Industrial and Applied Mathematics, 1467\u20131478."},{"key":"e_1_3_1_33_2","article-title":"On sampling edges almost uniformly","author":"Eden Talya","year":"2018","unstructured":"Talya Eden and Will Rosenbaum. 2018. On sampling edges almost uniformly. In Proceedings of the SIAM Symposium on Simplicity in Algorithms.","journal-title":"Proceedings of the SIAM Symposium on Simplicity in Algorithms"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2794080"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111011"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252"},{"key":"e_1_3_1_37_2","first-page":"25760","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","volume":"34","author":"Haddadan Shahrzad","year":"2021","unstructured":"Shahrzad Haddadan, Yue Zhuang, Cyrus Cousins, and Eli Upfal. 2021. Fast doubly-adaptive MCMC to estimate the Gibbs partition function with weak mixing time bounds. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 34, 25760\u201325772."},{"key":"e_1_3_1_38_2","first-page":"181","volume-title":"Proceedings of the IEEE 16th International Conference on Data Mining (ICDM \u201916).","author":"Han Guyue","year":"2016","unstructured":"Guyue Han and Harish Sethu. 2016. Waddling random walk: Fast and accurate mining of motif statistics in large graphs. In Proceedings of the IEEE 16th International Conference on Data Mining (ICDM \u201916). IEEE, 181\u2013190."},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-442450-0.50028-6"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1257\/aer.102.5.1857"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052636"},{"key":"e_1_3_1_42_2","unstructured":"Bai Jiang Qiang Sun and Jianqing Fan. 2018. Bernstein's inequality for general Markov chains. arXiv:1805.10721."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/1460797.1460799"},{"key":"e_1_3_1_44_2","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1007\/11533719_72","volume-title":"Proceedings of the International Computing and Combinatorics Conference","author":"Jowhari Hossein","year":"2005","unstructured":"Hossein Jowhari and Mohammad Ghodsi. 2005. New streaming algorithms for counting triangles in graphs. In Proceedings of the International Computing and Combinatorics Conference. Springer, 710\u2013716."},{"key":"e_1_3_1_45_2","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1007\/978-3-642-31585-5_53","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming","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 Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, 598\u2013609."},{"key":"e_1_3_1_46_2","first-page":"25","volume-title":"Proceedings of the ACM ASONAM","volume":"13","author":"Kang U.","year":"2013","unstructured":"U. Kang, Leman Akoglu, and Duen Horng Polo Chau. 2013. Big graph mining: Algorithms, anomaly detection, and applications. Proceedings of the ACM ASONAM 13 (2013), 25\u201328."},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2790304"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.625260"},{"key":"e_1_3_1_49_2","first-page":"12","article-title":"Visualizing plant metabolomic correlation networks using clique\u2013metabolite matrices","volume":"17","author":"Kose Frank","year":"2001","unstructured":"Frank Kose, Wolfram Weckwerth, Thomas Linke, and Oliver Fiehn. 2001. Visualizing plant metabolomic correlation networks using clique\u2013metabolite matrices. Bioinformatics 17, 12 (2001), 1198\u20131208.","journal-title":"Bioinformatics"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/107"},{"key":"e_1_3_1_52_2","volume-title":"Proceedings of the 12th ACM International Conference on Web Search and Data Mining","author":"Liu Paul","year":"2019","unstructured":"Paul Liu, Austin R. Benson, and Moses Charikar. 2019. Sampling methods for counting temporal motifs. In Proceedings of the 12th ACM International Conference on Web Search and Data Mining."},{"key":"e_1_3_1_53_2","first-page":"306","volume-title":"Proceedings of the IEEE Conference on Advanced Video and Signal Based Surveillance","author":"Liu Xiaoming","year":"2005","unstructured":"Xiaoming Liu, Peter Henry Tu, Jens Rittscher, Amitha Perera, and Nils Krahnstoever. 2005. Detecting and counting people in surveillance applications. In Proceedings of the IEEE Conference on Advanced Video and Signal Based Surveillance. IEEE, 306\u2013311."},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9338-2"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_3_1_58_2","first-page":"1","article-title":"Concentration inequalities for Markov chains by Marton couplings and spectral methods","volume":"20","author":"Paulin Daniel","year":"2012","unstructured":"Daniel Paulin. 2012. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability 20 (2012), 1\u201332.","journal-title":"Electronic Journal of Probability"},{"key":"e_1_3_1_59_2","first-page":"1870","volume-title":"Proceedings of the VLDB Endowment","volume":"6","author":"Pavan Aduri","year":"2013","unstructured":"Aduri Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. 2013. Counting and sampling triangles from a graph streams. Proceedings of the VLDB Endowment 6, 14 (2013, 1870\u20131881."},{"key":"e_1_3_1_60_2","first-page":"228","volume-title":"Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining","author":"Pei Jian","year":"2005","unstructured":"Jian Pei, Daxin Jiang, and Aidong Zhang. 2005. On mining cross-graph quasi-cliques. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 228\u2013238."},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.2297929"},{"key":"e_1_3_1_62_2","first-page":"1519","volume-title":"Proceedings of the 23rd ACM International CIKM (CIKM \u201914)","author":"Rahman Mahmudur","year":"2014","unstructured":"Mahmudur Rahman and Mohammad Al Hasan. 2014. Sampling triples from restricted networks using MCMC strategy. In Proceedings of the 23rd ACM International CIKM (CIKM \u201914), 1519\u20131528."},{"key":"e_1_3_1_63_2","doi-asserted-by":"crossref","first-page":"48","DOI":"10.3389\/fncom.2017.00048","article-title":"Cliques of neurons bound into cavities provide a missing link between structure and function","volume":"11","author":"Reimann Michael W.","year":"2017","unstructured":"Michael W. Reimann, Max Nolte, Martina Scolamiero, Katharine Turner, Rodrigo Perin, Giuseppe Chindemi, Pawe\u0142 D\u0142otko, Ran Levi, Kathryn Hess, and Henry Markram. 2017. Cliques of neurons bound into cavities provide a missing link between structure and function. Frontiers in Computational Neuroscience 11 (2017), 48.","journal-title":"Frontiers in Computational Neuroscience"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879192"},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2014.05.002"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_3_1_67_2","volume-title":"Proceedings of the 26th International Conference on Database Theory (ICDT \u201923)","author":"Seshadhri C.","year":"2023","unstructured":"C. Seshadhri. 2023. Some vignettes on subgraph counting using graph orientations (invited talk). In Proceedings of the 26th International Conference on Database Theory (ICDT \u201923). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_1_68_2","first-page":"75","volume-title":"Proceedings of the Web Conference (WWW \u201919)","volume":"2","author":"Seshadhri C.","year":"2019","unstructured":"C. Seshadhri and Srikanta Tirthapura. 2019. Scalable subgraph counting: The methods behind the madness: WWW 2019 tutorial. In Proceedings of the Web Conference (WWW \u201919), Vol. 2, 75."},{"issue":"4","key":"e_1_3_1_69_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3059194","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. 2017. Triest: Counting local and global triangles in fully dynamic streams with fixed memory size. ACM Transactions on Knowledge Discovery from Data (TKDD) 11, 4 (2017), 1\u201350.","journal-title":"ACM Transactions on Knowledge Discovery from Data (TKDD)"},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520059"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_3_1_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629564"},{"key":"e_1_3_1_74_2","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407840"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3699517","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,19]],"date-time":"2025-08-19T01:59:06Z","timestamp":1755568746000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3699517"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,18]]},"references-count":73,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1145\/3699517"],"URL":"https:\/\/doi.org\/10.1145\/3699517","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"type":"print","value":"2157-6904"},{"type":"electronic","value":"2157-6912"}],"subject":[],"published":{"date-parts":[[2025,8,18]]},"assertion":[{"value":"2024-01-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}