{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T16:22:05Z","timestamp":1772641325601,"version":"3.50.1"},"reference-count":80,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2024,10,9]],"date-time":"2024-10-09T00:00:00Z","timestamp":1728432000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the community detection problem in sparse random hypergraphs under the non-uniform hypergraph stochastic block model (HSBM), a general model of random networks with community structure and higher-order interactions. When the random hypergraph has bounded expected degrees, we provide a spectral algorithm that outputs a partition with at least a <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000166_inline1.png\"\/><jats:tex-math>$\\gamma$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> fraction of the vertices classified correctly, where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000166_inline2.png\"\/><jats:tex-math>$\\gamma \\in (0.5,1)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> depends on the signal-to-noise ratio (SNR) of the model. When the SNR grows slowly as the number of vertices goes to infinity, our algorithm achieves weak consistency, which improves the previous results in Ghoshdastidar and Dukkipati ((2017) <jats:italic>Ann. Stat.<\/jats:italic><jats:bold>45<\/jats:bold>(1) 289\u2013315.) for non-uniform HSBMs.<\/jats:p><jats:p>Our spectral algorithm consists of three major steps: (1) Hyperedge selection: select hyperedges of certain sizes to provide the maximal signal-to-noise ratio for the induced sub-hypergraph; (2) Spectral partition: construct a regularised adjacency matrix and obtain an approximate partition based on singular vectors; (3) Correction and merging: incorporate the hyperedge information from adjacency tensors to upgrade the error rate guarantee. The theoretical analysis of our algorithm relies on the concentration and regularisation of the adjacency matrix for sparse non-uniform random hypergraphs, which can be of independent interest.<\/jats:p>","DOI":"10.1017\/s0963548324000166","type":"journal-article","created":{"date-parts":[[2024,10,9]],"date-time":"2024-10-09T04:47:14Z","timestamp":1728449234000},"page":"1-51","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model"],"prefix":"10.1017","volume":"34","author":[{"given":"Ioana","family":"Dumitriu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hai-Xiao","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yizhe","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,10,9]]},"reference":[{"key":"S0963548324000166_ref19","unstructured":"[19] Chin, P. , Rao, A. and Van, V. (2015) Stochastic block model and community detection in sparse graphs: A spectral algorithm with optimal rate of recovery. In Conference on Learning Theory, pp. 391\u2013423."},{"key":"S0963548324000166_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/1873951.1874005"},{"key":"S0963548324000166_ref4","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.47"},{"key":"S0963548324000166_ref60","first-page":"849","volume-title":"Advances in Neural Information Processing Systems","author":"Ng","year":"2002"},{"key":"S0963548324000166_ref63","volume-title":"Advances in Neural Information Processing Systems, 27","author":"Saade","year":"2014"},{"key":"S0963548324000166_ref74","doi-asserted-by":"publisher","DOI":"10.1214\/21-AOS2099"},{"key":"S0963548324000166_ref75","article-title":"Community detection in censored hypergraph","author":"Yuan","year":"2021","journal-title":"Statistica Sinica"},{"key":"S0963548324000166_ref46","doi-asserted-by":"publisher","DOI":"10.1109\/JSAIT.2020.3037170"},{"key":"S0963548324000166_ref7","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2018.2837638"},{"key":"S0963548324000166_ref30","unstructured":"[30] Gaudio, Julia and Joshi, Nirmit (2023) Community detection in the hypergraph sbm: Optimal recovery given the similarity matrix. (Annual Conference Computational Learning Theory"},{"key":"S0963548324000166_ref61","first-page":"195","article-title":"Tensor sparsification via a bound on the spectral norm of random tensors","volume":"4","author":"Nguyen","year":"2015","journal-title":"Inf. Inference J. IMA"},{"key":"S0963548324000166_ref18","unstructured":"[18] Chin, B. and Sly, A. (2021) Optimal reconstruction of general sparse stochastic block models. arXiv preprint arXiv:2111.00697."},{"key":"S0963548324000166_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-015-0659-z"},{"key":"S0963548324000166_ref22","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOP1180"},{"key":"S0963548324000166_ref24","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2023.3302283"},{"key":"S0963548324000166_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2020.01.039"},{"key":"S0963548324000166_ref38","doi-asserted-by":"publisher","DOI":"10.1137\/20M1379745"},{"key":"S0963548324000166_ref27","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2966438"},{"key":"S0963548324000166_ref73","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33018981"},{"key":"S0963548324000166_ref69","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"S0963548324000166_ref1","first-page":"1","article-title":"Community detection and stochastic block models: Recent developments","volume":"18","author":"Abbe","year":"2018","journal-title":"J. Mach. Learn. Res."},{"key":"S0963548324000166_ref72","unstructured":"[72] Wang, J. , Pun, Y.-M. , Wang, X. , Wang, P. and So, A. M.-C. (2023) Projected tensor power method for hypergraph community recovery. In International Conference on Machine Learning, PMLR, pp. 36285\u201336307."},{"key":"S0963548324000166_ref59","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.012582999"},{"key":"S0963548324000166_ref40","first-page":"1431","volume-title":"Advances in Neural Information Processing Systems","author":"Jain","year":"2014"},{"key":"S0963548324000166_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-32296-9_6"},{"key":"S0963548324000166_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990514"},{"key":"S0963548324000166_ref42","unstructured":"[42] Ke, Z. T. , Shi, F. and Xia, D. (2019) Community detection for hypergraph networks via regularized tensor power iteration. arXiv preprint arXiv:1909.06503."},{"key":"S0963548324000166_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/JHEP11(2021)015"},{"key":"S0963548324000166_ref36","unstructured":"[36] Gu, Y. and Polyanskiy, Y. (2023) Weak recovery threshold for the hypergraph stochastic block model. In The Thirty Sixth Annual Conference on Learning Theory, PMLR, pp. 885\u2013920."},{"key":"S0963548324000166_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2016.7852294"},{"key":"S0963548324000166_ref54","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897548"},{"key":"S0963548324000166_ref33","first-page":"1638","article-title":"Uniform hypergraph partitioning: Provable tensor methods and sampling techniques","volume":"18","author":"Ghoshdastidar","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"S0963548324000166_ref70","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1017\/S0963548317000463","article-title":"A simple svd algorithm for finding hidden partitions","volume":"27","author":"Van","year":"2018","journal-title":"Comb. Probab. Comput."},{"key":"S0963548324000166_ref9","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2015.7446987"},{"key":"S0963548324000166_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2020.05.004"},{"key":"S0963548324000166_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2020.03.013"},{"key":"S0963548324000166_ref44","doi-asserted-by":"publisher","DOI":"10.1214\/21-EJS1971"},{"key":"S0963548324000166_ref47","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/asz068"},{"key":"S0963548324000166_ref28","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20089"},{"key":"S0963548324000166_ref41","volume-title":"Advances in Neural Information Processing Systems, 34","author":"Jin","year":"2021"},{"key":"S0963548324000166_ref52","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591857"},{"key":"S0963548324000166_ref62","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21006"},{"key":"S0963548324000166_ref35","unstructured":"[35] Gu, Y. and Pandey, A. (2024) Community detection in the hypergraph stochastic block model and reconstruction on hypertrees. arXiv preprint arXiv:2402.06856."},{"key":"S0963548324000166_ref43","unstructured":"[43] Kim, C. , Bandeira, A. S. and Goemans, M. X. (2018) Stochastic block model for hypergraphs: Statistical limits and a semidefinite programming approach. arXiv preprint arXiv:1807.02884."},{"key":"S0963548324000166_ref31","first-page":"397","volume-title":"Advances in Neural Information Processing Systems","author":"Ghoshdastidar","year":"2014"},{"key":"S0963548324000166_ref64","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20774"},{"key":"S0963548324000166_ref15","doi-asserted-by":"publisher","DOI":"10.1561\/2200000079"},{"key":"S0963548324000166_ref51","doi-asserted-by":"publisher","DOI":"10.1007\/s11192-018-2908-2"},{"key":"S0963548324000166_ref53","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.86.056111"},{"key":"S0963548324000166_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21719"},{"key":"S0963548324000166_ref45","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20713"},{"key":"S0963548324000166_ref65","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","article-title":"Normalized cuts and image segmentation","volume":"22","author":"Shi","year":"2000","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"S0963548324000166_ref32","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1453"},{"key":"S0963548324000166_ref39","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"S0963548324000166_ref79","first-page":"1601","volume-title":"Advances in Neural Information Processing Systems","author":"Zhou","year":"2007"},{"key":"S0963548324000166_ref3","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1854"},{"key":"S0963548324000166_ref12","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOP1142"},{"key":"S0963548324000166_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294459"},{"key":"S0963548324000166_ref78","first-page":"1","article-title":"Community detection in general hypergraph via graph embedding","author":"Zhen","year":"2022","journal-title":"J. Am. Stat. Assoc."},{"key":"S0963548324000166_ref58","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3238-8"},{"key":"S0963548324000166_ref11","doi-asserted-by":"publisher","DOI":"10.1126\/science.aad9029"},{"key":"S0963548324000166_ref49","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433436"},{"key":"S0963548324000166_ref25","unstructured":"[25] Dumitriu, I. and Wang, H. (2023) Optimal and exact recovery on general non-uniform hypergraph stochastic block model. arXiv preprint arXiv:2304.13139."},{"key":"S0963548324000166_ref66","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.159"},{"key":"S0963548324000166_ref71","unstructured":"[71] Wang, H. (2023) Fundamental limits and strong consistency of binary non-uniform hypergraph stochastic block models."},{"key":"S0963548324000166_ref76","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOS1428"},{"key":"S0963548324000166_ref80","doi-asserted-by":"publisher","DOI":"10.1214\/21-EJS1838"},{"key":"S0963548324000166_ref34","doi-asserted-by":"crossref","unstructured":"[34] Govindu, V. M. (2005) A tensor decomposition for geometric grouping and segmentation. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201905), IEEE, pp. 1150\u20131157, vol. 1.","DOI":"10.1109\/CVPR.2005.50"},{"key":"S0963548324000166_ref55","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-014-0576-6"},{"key":"S0963548324000166_ref56","doi-asserted-by":"publisher","DOI":"10.1214\/15-AAP1145"},{"key":"S0963548324000166_ref16","unstructured":"[16] Chien, I., Lin, Chung-Yi and Wang, I.-Hsiang (2018) Community detection in hypergraphs: Optimal statistical limit and efficient algorithms. In International Conference on Artificial Intelligence and Statistics, pp. 871\u2013879."},{"key":"S0963548324000166_ref17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2928301"},{"key":"S0963548324000166_ref2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2490670"},{"key":"S0963548324000166_ref68","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp467"},{"key":"S0963548324000166_ref67","first-page":"iaae004","article-title":"Sparse random hypergraphs: Non-backtracking spectra and community detection","volume":"13","author":"Stephan","year":"2024","journal-title":"Inf. Inference J. IMA"},{"key":"S0963548324000166_ref26","doi-asserted-by":"publisher","DOI":"10.37236\/8741"},{"key":"S0963548324000166_ref50","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2017.8006915"},{"key":"S0963548324000166_ref77","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3205959"},{"key":"S0963548324000166_ref57","doi-asserted-by":"publisher","DOI":"10.1214\/16-EJP4185"},{"key":"S0963548324000166_ref48","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1274"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000166","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T09:51:32Z","timestamp":1740390692000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000166\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,9]]},"references-count":80,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["S0963548324000166"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000166","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,9]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}