{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:48:28Z","timestamp":1761324508051,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":59,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T00:00:00Z","timestamp":1677456000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF-TRIPODS"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,2,27]]},"DOI":"10.1145\/3539597.3570438","type":"proceedings-article","created":{"date-parts":[[2023,2,22]],"date-time":"2023-02-22T23:27:00Z","timestamp":1677108420000},"page":"312-320","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["DeMEtRIS: Counting (near)-Cliques by Crawling"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5699-2948","authenticated-orcid":false,"given":"Suman K.","family":"Bera","sequence":"first","affiliation":[{"name":"Katana Graph, 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, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7702-8250","authenticated-orcid":false,"given":"Shahrzad","family":"Haddadan","sequence":"additional","affiliation":[{"name":"Rutgers Business School and Brown Data Science Initiative, New Brunswick, 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":[[2023,2,27]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"[n.d.]. Facebook User Public API. https:\/\/developers.facebook.com\/docs\/graph-api\/reference\/user\/. Accessed: 2022-01--31."},{"key":"e_1_3_2_2_2_1","unstructured":"[n.d.]. Twitter Public API. https:\/\/developer.twitter.com\/en\/docs\/twitter-api\/v1\/accounts-and-users\/follow-search-get-users\/overview. Accessed: 2022-01--31."},{"key":"e_1_3_2_2_3_1","volume-title":"CFinder: locating cliques and overlapping modules in biological networks. Bioinformatics","author":"Adamcsek Bal\u00e1zs","year":"2006","unstructured":"Bal\u00e1zs Adamcsek, Gergely Palla, Ill\u00e9s J Farkas, Imre Der\u00e9nyi, and Tam\u00e1s Vicsek. 2006. CFinder: locating cliques and overlapping modules in biological networks. Bioinformatics (2006)."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Matteo Agostini Marco Bressan and Shahrzad Haddadan. 2019. Mixing time bounds for graphlet random walks. Inform. Process. Lett. (2019).","DOI":"10.1016\/j.ipl.2019.105851"},{"key":"e_1_3_2_2_5_1","volume-title":"Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee.","author":"Aliakbarpour Maryam","year":"2018","unstructured":"Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee. 2018. Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling. Algorithmica (2018)."},{"key":"e_1_3_2_2_6_1","unstructured":"Sepehr Assadi Mikhail Kapralov and Sanjeev Khanna. 2019. A Simple Sublinear- Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In ITCS."},{"key":"e_1_3_2_2_7_1","volume-title":"Efficient algorithms for large-scale local triangle counting. ACM Transactions on Knowledge Discovery from Data (TKDD)","author":"Becchetti Luca","year":"2010","unstructured":"Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. 2010. Efficient algorithms for large-scale local triangle counting. ACM Transactions on Knowledge Discovery from Data (TKDD) (2010)."},{"key":"e_1_3_2_2_8_1","volume-title":"Sampling Multiple Nodes in Large Networks: Beyond Random Walks. arXiv preprint arXiv:2110.13324","author":"Ben-Eliezer Omri","year":"2021","unstructured":"Omri Ben-Eliezer, Talya Eden, Joel Oren, and Dimitris Fotakis. 2021. Sampling Multiple Nodes in Large Networks: Beyond Random Walks. arXiv preprint arXiv:2110.13324 (2021)."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175416"},{"key":"e_1_3_2_2_10_1","volume-title":"The mixing time of the giant component of a random graph. Random Structures & Algorithms","author":"Benjamini Itai","year":"2014","unstructured":"Itai Benjamini, Gady Kozma, and Nicholas Wormald. 2014. The mixing time of the giant component of a random graph. Random Structures & Algorithms (2014)."},{"key":"e_1_3_2_2_11_1","volume-title":"Proc. 34th of International Symposium on Theoretical Aspects of Computer Science.","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 Proc. 34th of International Symposium on Theoretical Aspects of Computer Science."},{"volume-title":"Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS'20)","author":"Bera Suman K.","key":"e_1_3_2_2_12_1","unstructured":"Suman K. Bera and C. Seshadhri. 2020. How the Degeneracy Helps for Triangle Counting in Graph Streams. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS'20). Association for Computing Machinery."},{"volume-title":"Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery &; Data Mining","author":"Bera Suman K.","key":"e_1_3_2_2_13_1","unstructured":"Suman K. Bera and C. Seshadhri. 2020. How to Count Triangles, without Seeing the Whole Graph. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery &; Data Mining (Virtual Event, CA, USA) (KDD '20). Association for Computing Machinery."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021940"},{"key":"e_1_3_2_2_16_1","volume-title":"International World Wide Web Conferences Steering Committee.","author":"Chiericetti Flavio","year":"2016","unstructured":"Flavio Chiericetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi, and Tam\u00e1s Sarl\u00f3s. 2016. On Sampling Nodes in a Network (WWW '16). International World Wide Web Conferences Steering Committee."},{"key":"e_1_3_2_2_17_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Chierichetti Flavio","year":"2018","unstructured":"Flavio Chierichetti and Shahrzad Haddadan. 2018. On the Complexity of Sampling Vertices Uniformly from a Graph. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_18_1","volume-title":"Social capital in the creation of human capital. American journal of sociology","author":"Coleman James S","year":"1988","unstructured":"James S Coleman. 1988. Social capital in the creation of human capital. American journal of sociology (1988)."},{"key":"e_1_3_2_2_19_1","volume-title":"Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE. arXiv preprint arXiv:2011.11129","author":"Cousins Cyrus","year":"2020","unstructured":"Cyrus Cousins, Shahrzad Haddadan, and Eli Upfal. 2020. Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE. arXiv preprint arXiv:2011.11129 (2020)."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568019"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186111"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054389"},{"volume-title":"Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '20)","author":"Eden Talya","key":"e_1_3_2_2_24_1","unstructured":"Talya Eden, Dana Ron, and C. Seshadhri. [n.d.]. Faster Sublinear Approximation of the Number of k-Cliques in Low-Arboricity Graphs. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '20). Society for Industrial and Applied Mathematics."},{"key":"e_1_3_2_2_25_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming (ICALP","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 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188810"},{"key":"e_1_3_2_2_27_1","volume-title":"On Sampling Edges Almost Uniformly. In SIAM Symposium on Simplicity in Algorithms.","author":"Eden Talya","year":"2018","unstructured":"Talya Eden and Will Rosenbaum. 2018. On Sampling Edges Almost Uniformly. In SIAM Symposium on Simplicity in Algorithms."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2794080"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111011"},{"volume-title":"Introduction to property testing","author":"Goldreich Oded","key":"e_1_3_2_2_30_1","unstructured":"Oded Goldreich. 2017. Introduction to property testing. Cambridge University Press."},{"volume-title":"Social networks","author":"Holland Paul W","key":"e_1_3_2_2_31_1","unstructured":"Paul W Holland and Samuel Leinhardt. [n.d.]. A method for detecting structure in sociometric data. In Social networks. Elsevier."},{"key":"e_1_3_2_2_32_1","volume-title":"Social capital and social quilts: Network patterns of favor exchange. American Economic Review","author":"Jackson Matthew O","year":"2012","unstructured":"Matthew O Jackson, Tomas Rodriguez-Barraquer, and Xu Tan. 2012. Social capital and social quilts: Network patterns of favor exchange. American Economic Review (2012)."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052636"},{"key":"e_1_3_2_2_34_1","volume-title":"Mining frequent cross-graph quasi-cliques. ACM Transactions on Knowledge Discovery from Data (TKDD)","author":"Jiang Daxin","year":"2009","unstructured":"Daxin Jiang and Jian Pei. 2009. Mining frequent cross-graph quasi-cliques. ACM Transactions on Knowledge Discovery from Data (TKDD) (2009)."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11533719_72"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"crossref","unstructured":"Daniel M Kane Kurt Mehlhorn Thomas Sauerwald and He Sun. 2012. Counting arbitrary subgraphs in data streams. In International Colloquium on Automata Languages and Programming.","DOI":"10.1007\/978-3-642-31585-5_53"},{"key":"e_1_3_2_2_37_1","volume-title":"Proceedings of the ACM ASONAM","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 (2013)."},{"key":"e_1_3_2_2_38_1","volume-title":"Hardiman","author":"Katzir Liran","year":"2015","unstructured":"Liran Katzir and Stephen J. Hardiman. 2015. Estimating Clustering Coefficients and Size of Social Networks via Random Walk. ACM Trans. Web (2015)."},{"key":"e_1_3_2_2_39_1","volume-title":"Visualizing plant metabolomic correlation networks using clique--metabolite matrices. Bioinformatics","author":"Kose Frank","year":"2001","unstructured":"Frank Kose, Wolfram Weckwerth, Thomas Linke, and Oliver Fiehn. 2001. Visualizing plant metabolomic correlation networks using clique--metabolite matrices. Bioinformatics (2001)."},{"key":"e_1_3_2_2_40_1","volume-title":"Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics","author":"Leskovec Jure","year":"2009","unstructured":"Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. 2009. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics (2009)."},{"volume-title":"Markov chains and mixing times","author":"Levin David A","key":"e_1_3_2_2_41_1","unstructured":"David A Levin and Yuval Peres. 2017. Markov chains and mixing times. Vol. 107. American Mathematical Soc."},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3290988"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/AVSS.2005.1577286"},{"key":"e_1_3_2_2_44_1","volume-title":"Combinatorial algorithms for the maximum k-plex problem. Journal of combinatorial optimization","author":"McClosky Benjamin","year":"2012","unstructured":"Benjamin McClosky and Illya V Hicks. 2012. Combinatorial algorithms for the maximum k-plex problem. Journal of combinatorial optimization (2012)."},{"key":"e_1_3_2_2_45_1","unstructured":"Itzkovitz S Kashtan N Chklovskii D Alon U Milo R Shen-Orr S. 2002. Network motifs: simple building blocks of complex networks. In Science."},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_3_2_2_47_1","volume-title":"Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability","author":"Paulin Daniel","year":"2012","unstructured":"Daniel Paulin. 2012. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability (2012)."},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081898"},{"key":"e_1_3_2_2_50_1","volume-title":"Mansurul Alam Bhuiyan, and Mohammad Al Hasan","author":"Rahman Mahmudur","year":"2014","unstructured":"Mahmudur Rahman, Mansurul Alam Bhuiyan, and Mohammad Al Hasan. 2014. Graft: An Efficient Graphlet Counting Method for Large Graph Analysis. IEEE Transactions on Knowledge and Data Engineering (2014)."},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2662075"},{"key":"e_1_3_2_2_52_1","volume-title":"Cliques of neurons bound into cavities provide a missing link between structure and function. Frontiers in computational neuroscience","author":"Reimann Michael W","year":"2017","unstructured":"Michael W Reimann, Max Nolte, Martina Scolamiero, Katharine Turner, Rodrigo Perin, Giuseppe Chindemi, Pawel Dlotko, 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 (2017)."},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879192"},{"key":"e_1_3_2_2_54_1","volume-title":"Anomaly detection in online social networks. Social networks","author":"Savage David","year":"2014","unstructured":"David Savage, Xiuzhen Zhang, Xinghuo Yu, Pauline Chou, and Qingmai Wang. 2014. Anomaly detection in online social networks. Social networks (2014)."},{"key":"e_1_3_2_2_55_1","volume-title":"A graph-theoretic generalization of the clique concept. Journal of Mathematical sociology","author":"Seidman Stephen B","year":"1978","unstructured":"Stephen B Seidman and Brian L Foster. 1978. A graph-theoretic generalization of the clique concept. Journal of Mathematical sociology (1978)."},{"key":"e_1_3_2_2_56_1","volume-title":"Proceedings of the Web Conference (WWW).","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)."},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3059194"},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520059"},{"key":"e_1_3_2_2_59_1","volume-title":"Bruno Ribeiro, Don Towsley, Junzhou Zhao, and Xiaohong Guan.","author":"Wang Pinghui","year":"2014","unstructured":"Pinghui Wang, John CS Lui, Bruno Ribeiro, Don Towsley, Junzhou Zhao, and Xiaohong Guan. 2014. Efficiently estimating motif statistics of large networks. ACM Transactions on Knowledge Discovery from Data (TKDD) (2014)."}],"event":{"name":"WSDM '23: The Sixteenth ACM International Conference on Web Search and Data Mining","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data","SIGIR ACM Special Interest Group on Information Retrieval"],"location":"Singapore Singapore","acronym":"WSDM '23"},"container-title":["Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3539597.3570438","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3539597.3570438","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:14Z","timestamp":1750186934000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3539597.3570438"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,27]]},"references-count":59,"alternative-id":["10.1145\/3539597.3570438","10.1145\/3539597"],"URL":"https:\/\/doi.org\/10.1145\/3539597.3570438","relation":{},"subject":[],"published":{"date-parts":[[2023,2,27]]},"assertion":[{"value":"2023-02-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}