{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T17:38:52Z","timestamp":1790185132743,"version":"4.1.0"},"reference-count":58,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"Eric and Wendy Schmidt Fellowship"},{"DOI":"10.13039\/501100005155","name":"Azrieli Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005155","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011643","name":"Blavatnik Family Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100011643","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["671\/13"],"award-info":[{"award-number":["671\/13"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1146\/18"],"award-info":[{"award-number":["1146\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1740751"],"award-info":[{"award-number":["1740751"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We study the problem of approximating the number of $k$-cliques in a graph when given query access to the graph. We consider the standard query model for general graphs via (1) degree queries, (2) neighbor queries, and (3) pair queries. Let $n$ denote the number of vertices in the graph, $m$ the number of edges, and $C_k$ the number of $k$-cliques. We design an algorithm that outputs a $(1+\\varepsilon)$-approximation (with high probability) for $C_k$, whose expected query complexity and running time are $O(\\frac{n}{C_k^{1\/k}}+\\frac{m^{k\/2}}{C_k} ){poly}(\\log n, 1\/\\varepsilon,k)$. Hence, the complexity of the algorithm is sublinear in the size of the graph for $C_k = \\omega(m^{k\/2-1})$. Furthermore, we prove a lower bound showing that the query complexity of our algorithm is essentially optimal (up to the dependence on $\\log n$, $1\/\\varepsilon$, and $k$). The previous results in this vein are by Feige [ SIAM J. Comput., 35 (2006), pp. 964--984] and by Goldreich and Ron [ Random Structures Algorithms, 32 (2008), pp. 473--493] for edge counting ($k=2$) and by Eden, Levi, Ron, and Seshadhri [ SIAM J. Comput., 46 (2017), pp. 1603--1646] for triangle counting ($k=3$). Our result matches the complexities of these results. The previous result by Eden et al. hinges on a certain amortization technique that works only for triangle counting and does not generalize for larger cliques. We obtain a general algorithm that works for any $k\\geq 3$ by designing a procedure that samples each $k$-clique incident to one of the vertices of a given set $S$ of vertices with approximately equal probability.<\/jats:p>","DOI":"10.1137\/18m1176701","type":"journal-article","created":{"date-parts":[[2020,7,14]],"date-time":"2020-07-14T12:02:56Z","timestamp":1594728176000},"page":"747-771","source":"Crossref","is-referenced-by-count":9,"title":["On Approximating the Number of $k$-Cliques in Sublinear Time"],"prefix":"10.1137","volume":"49","author":[{"given":"Talya","family":"Eden","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,7,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"A. Abboud, A. Backurs, and V. V. Williams,\n                      If the current clique algorithms are optimal, so is Valiant's parser\n                      , in Proceedings of the Symposium on Foundations of Computer Science (FOCS), 2015, pp. 98-117.","DOI":"10.1109\/FOCS.2015.16"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"K. J. Ahn, S. Guha, and A. McGregor,\n                      Graph sketches: Sparsification, spanners, and subgraphs\n                      , in Proceedings of the Symposium on Principles of Database Systems (PODS), 2012, pp. 5-14.","DOI":"10.1145\/2213556.2213560"},{"key":"atypb3","unstructured":"H. Avron,\n                      Counting triangles in large graphs using randomized matrix trace estimation\n                      , in Proceedings of the Workshop on Large-scale Data Mining: Theory and Applications (LDMTA), 2010, pp. 10-9."},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"L. Becchetti, P. Boldi, C. Castillo, and A. Gionis,\n                      Efficient semi-streaming algorithms for local triangle counting in massive graphs\n                      , in Proceedings of the International Conference on Knowledge Discovery and Data Mining (SIGKDD), 2008, pp. 16-24.","DOI":"10.1145\/1401890.1401898"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.056119"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1086\/421787"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"F. Chierichetti, A. Dasgupta, R. Kumar, S. Lattanzi, and T. Sarlos,\n                      On sampling nodes in a network\n                      , in Proceedings of the Conference on the World Wide Web (WWW), 2016, pp. 471-481.","DOI":"10.1145\/2872427.2883045"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"S. Chu and J. Cheng,\n                      Triangle listing in massive networks and its applications\n                      , in Proceedings of the International Conference on Knowledge Discovery and Data Mining (SIGKDD), 2011, pp. 672-680.","DOI":"10.1145\/2020408.2020513"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1086\/228943"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435297"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/060672121"},{"key":"atypb15","first-page":"795","author":"Dasgupta A.","year":"2014","journal-title":"ACM"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.032093399"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054389"},{"key":"atypb18","unstructured":"T. Eden, D. Ron, and C. Seshadhri,\n                      On Approximating the Number of $k$-Cliques in Sublinear Time\n                      , CoRR, abs\/1707.04858v1, 2017,https:\/\/arxiv.org\/abs\/1707.04858v1."},{"key":"atypb19","unstructured":"T. Eden, D. Ron, and C. Seshadhri,\n                      Sublinear time estimation of degree distribution moments: The degeneracy connection\n                      , in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, 2017,https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.7."},{"key":"atypb20","unstructured":"T. Eden and W. Rosenbaum,\n                      Lower Bounds for Approximating Graph Parameters via Communication Complexity\n                      , CoRR, abs\/1709.04262, 2017,https:\/\/arxiv.org\/abs\/1709.04262."},{"key":"atypb21","first-page":"1","author":"Eden T.","year":"2018","journal-title":"LA"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/2543629"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704447304"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/2794080"},{"key":"atypb26","first-page":"4027","author":"Welles B. Foucault","year":"2010","journal-title":"Proceedings of the CHI Conference on Human Factors in Computing Systems"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"O. Goldreich,\n                      Introduction to Property Testing\n                      , Cambridge University Press, Cambridge, UK, 2017.","DOI":"10.1017\/9781108135252"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20203"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/100783066"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"A. Hassidim, J. A. Kelner, H. N. Nguyen, and K. Onak,\n                      Local graph partitions for approximation and testing\n                      , in Proceedings of the Symposium on Foundations of Computer Science (FOCS), 2009, pp. 22-31.","DOI":"10.1109\/FOCS.2009.77"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1086\/224954"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1257\/aer.102.5.1857"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"S. Jain and C. Seshadhri,\n                      A fast and provable method for estimating clique counts using Tur\u00e1n's theorem\n                      , in Proceedings of the Conference on the World Wide Web (WWW), 2017, pp. 441-449.","DOI":"10.1145\/3038912.3052636"},{"key":"atypb34","first-page":"710","author":"Jowhari H.","year":"2005","journal-title":"Springer"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"D. M. Kane, K. Mehlhorn, T. Sauerwald, and H. Sun,\n                      Counting arbitrary subgraphs in data streams\n                      , in Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), 2012, pp. 598-609.","DOI":"10.1007\/978-3-642-31585-5_53"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.625260"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1145\/1497290.1497298"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v011.i03"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"atypb40","first-page":"415","volume":"26","author":"Ne\u0161t\u0159il J.","year":"1985","journal-title":"Comment. Math. Univ. Carolin."},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"H. N. Nguyen and K. Onak,\n                      Constant-time approximation algorithms via local improvements\n                      , in Proceedings of the Symposium on Foundations of Computer Science (FOCS), 2008, pp. 327-336.","DOI":"10.1109\/FOCS.2008.81"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"K. Onak, D. Ron, M. Rosen, and R. Rubinfeld,\n                      A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size\n                      , in Proceedings of the Symposium on Discrete Algorithms (SODA), 2012, pp. 1123-1131.","DOI":"10.1137\/1.9781611973099.88"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.040"},{"key":"atypb44","first-page":"43","author":"Portes A.","year":"2000","journal-title":"MA"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00108"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.85.056109"},{"key":"atypb48","unstructured":"C. Seshadhri, A. Pinar, and T. G. Kolda,\n                      Fast triangle counting through wedge sampling\n                      , in Proceedings of the International Conference on Data Mining (ICDM), 2013, p. 5."},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"S. Suri and S. Vassilvitskii,\n                      Counting triangles and the curse of the last reducer\n                      , in Proceedings of the International Conference on World Wide Web (WWW), 2011, pp. 607-614,https:\/\/doi.org\/10.1145\/1963405.1963491.","DOI":"10.1145\/1963405.1963491"},{"key":"atypb50","first-page":"781","author":"Tangwongsan K.","year":"2013","journal-title":"ACM"},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"C. E. Tsourakakis,\n                      Fast counting of triangles in large real networks without counting: Algorithms and laws\n                      , in Proceedings of the International Conference on Data Mining (ICDM), 2008, pp. 608-617.","DOI":"10.1109\/ICDM.2008.72"},{"key":"atypb52","doi-asserted-by":"crossref","unstructured":"C. E. Tsourakakis,\n                      The k-clique densest subgraph problem\n                      , in Proceedings of the International Conference on World Wide Web (WWW), 2015, pp. 1122-1132,https:\/\/doi.org\/10.1145\/2736277.2741098.","DOI":"10.1145\/2736277.2741098"},{"key":"atypb53","doi-asserted-by":"crossref","unstructured":"C. E. Tsourakakis, U. Kang, G. Miller, and C. Faloutsos,\n                      Doulion: Counting triangles in massive graphs with a coin\n                      , in Proceedings of the International Conference on Knowledge Discovery and Data Mining (SIGKDD), 2009, pp. 837-846.","DOI":"10.1145\/1557019.1557111"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00245"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.10.014"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1049\/el:19740097"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355749"},{"key":"atypb58","doi-asserted-by":"crossref","unstructured":"Y. Yoshida, M. Yamamoto, and H. Ito,\n                      An improved constant-time approximation algorithm for maximum\n                      , in Proceedings of the Symposium on Theory of Computing (STOC), 2009, pp. 225-234.","DOI":"10.1145\/1536414.1536447"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1176701","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:24:58Z","timestamp":1787336698000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1176701"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":58,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1176701"],"URL":"https:\/\/doi.org\/10.1137\/18m1176701","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}