IDEAS home Printed from https://ideas.repec.org/a/eee/csdana/v190y2024ics0167947323001834.html
   My bibliography  Save this article

On the efficacy of higher-order spectral clustering under weighted stochastic block models

Author

Listed:
  • Guo, Xiao
  • Zhang, Hai
  • Chang, Xiangyu

Abstract

Higher-order structures of networks, namely, small subgraphs of networks (also called network motifs), are widely known to be crucial and essential to the organization of networks. Several works have studied the community detection problem–a fundamental problem in network analysis at the level of motifs. In particular, the higher-order spectral clustering has been developed, where the notion of motif adjacency matrix is introduced as the algorithm's input. However, how the higher-order spectral clustering works and when it performs better than its edge-based counterpart remain largely unknown. To elucidate these problems, the higher-order spectral clustering is investigated from a statistical perspective. The clustering performance of the higher-order spectral clustering is theoretically studied under a weighted stochastic block model, and the resulting bounds are compared with the corresponding results of the edge-based spectral clustering. The upper bounds and simulations show that when the network is dense and the edge weights have a weak signal, higher-order spectral clustering can lead to a performance gain in clustering. Real data experiments also corroborate the merits of higher-order spectral clustering.

Suggested Citation

  • Guo, Xiao & Zhang, Hai & Chang, Xiangyu, 2024. "On the efficacy of higher-order spectral clustering under weighted stochastic block models," Computational Statistics & Data Analysis, Elsevier, vol. 190(C).
    • Handle: RePEc:eee:csdana:v:190:y:2024:i:c:s0167947323001834
    DOI: 10.1016/j.csda.2023.107872
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0167947323001834
    Download Restriction: Full text for ScienceDirect subscribers only.
    File URL: https://libkey.io/10.1016/j.csda.2023.107872?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Vishesh Karwa & Pavel N. Krivitsky & Aleksandra B. Slavković, 2017. "Sharing social network data: differentially private estimation of exponential family random-graph models," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 66(3), pages 481-500, April.
    2. Martin Rosvall & Alcides V. Esquivel & Andrea Lancichinetti & Jevin D. West & Renaud Lambiotte, 2014. "Memory in network flows and its effects on spreading dynamics and community detection," Nature Communications, Nature, vol. 5(1), pages 1-13, December.
    3. Tianxi Li & Elizaveta Levina & Ji Zhu, 2020. "Network cross-validation by edge sampling," Biometrika, Biometrika Trust, vol. 107(2), pages 257-276.
    4. Bo Wang & Armin Pourshafeie & Marinka Zitnik & Junjie Zhu & Carlos D. Bustamante & Serafim Batzoglou & Jure Leskovec, 2018. "Network enhancement as a general method to denoise weighted biological networks," Nature Communications, Nature, vol. 9(1), pages 1-8, December.
    5. Ming Yuan & Yi Lin, 2007. "Model selection and estimation in the Gaussian graphical model," Biometrika, Biometrika Trust, vol. 94(1), pages 19-35.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Chao Min & Qingyu Chen & Erjia Yan & Yi Bu & Jianjun Sun, 2021. "Citation cascade and the evolution of topic relevance," Journal of the Association for Information Science & Technology, Association for Information Science & Technology, vol. 72(1), pages 110-127, January.
    2. Avagyan, Vahe & Nogales, Francisco J., 2015. "D-trace Precision Matrix Estimation Using Adaptive Lasso Penalties," DES - Working Papers. Statistics and Econometrics. WS 21775, Universidad Carlos III de Madrid. Departamento de Estadística.
    3. Byrd, Michael & Nghiem, Linh H. & McGee, Monnie, 2021. "Bayesian regularization of Gaussian graphical models with measurement error," Computational Statistics & Data Analysis, Elsevier, vol. 156(C).
    4. Duo Jiang & Thomas Sharpton & Yuan Jiang, 2021. "Microbial Interaction Network Estimation via Bias-Corrected Graphical Lasso," Statistics in Biosciences, Springer;International Chinese Statistical Association, vol. 13(2), pages 329-350, July.
    5. Ding, Yi & Li, Yingying & Liu, Guoli & Zheng, Xinghua, 2024. "Stock co-jump networks," Journal of Econometrics, Elsevier, vol. 239(2).
    6. Lam, Clifford, 2008. "Estimation of large precision matrices through block penalization," LSE Research Online Documents on Economics 31543, London School of Economics and Political Science, LSE Library.
    7. Giraud Christophe & Huet Sylvie & Verzelen Nicolas, 2012. "Graph Selection with GGMselect," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 11(3), pages 1-52, February.
    8. Seunghwan Lee & Sang Cheol Kim & Donghyeon Yu, 2023. "An efficient GPU-parallel coordinate descent algorithm for sparse precision matrix estimation via scaled lasso," Computational Statistics, Springer, vol. 38(1), pages 217-242, March.
    9. Yuan, Quan & Liu, Binghui, 2021. "Community detection via an efficient nonconvex optimization approach based on modularity," Computational Statistics & Data Analysis, Elsevier, vol. 157(C).
    10. Chakraborty, Abhijit & Krichene, Hazem & Inoue, Hiroyasu & Fujiwara, Yoshi, 2019. "Characterization of the community structure in a large-scale production network in Japan," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 513(C), pages 210-221.
    11. Benjamin Poignard & Manabu Asai, 2023. "Estimation of high-dimensional vector autoregression via sparse precision matrix," The Econometrics Journal, Royal Economic Society, vol. 26(2), pages 307-326.
    12. Dong Liu & Changwei Zhao & Yong He & Lei Liu & Ying Guo & Xinsheng Zhang, 2023. "Simultaneous cluster structure learning and estimation of heterogeneous graphs for matrix‐variate fMRI data," Biometrics, The International Biometric Society, vol. 79(3), pages 2246-2259, September.
    13. Mehran Aflakparast & Mathisca de Gunst & Wessel van Wieringen, 2020. "Analysis of Twitter data with the Bayesian fused graphical lasso," PLOS ONE, Public Library of Science, vol. 15(7), pages 1-28, July.
    14. Gong, Chang & Li, Jichao & Qian, Liwei & Li, Siwei & Yang, Zhiwei & Yang, Kewei, 2024. "HMSL: Source localization based on higher-order Markov propagation," Chaos, Solitons & Fractals, Elsevier, vol. 182(C).
    15. Huangdi Yi & Qingzhao Zhang & Cunjie Lin & Shuangge Ma, 2022. "Information‐incorporated Gaussian graphical model for gene expression data," Biometrics, The International Biometric Society, vol. 78(2), pages 512-523, June.
    16. Byol Kim & Song Liu & Mladen Kolar, 2021. "Two‐sample inference for high‐dimensional Markov networks," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 83(5), pages 939-962, November.
    17. He, Yong & Zhang, Xinsheng & Wang, Pingping & Zhang, Liwen, 2017. "High dimensional Gaussian copula graphical model with FDR control," Computational Statistics & Data Analysis, Elsevier, vol. 113(C), pages 457-474.
    18. Yong Cai, 2022. "Linear Regression with Centrality Measures," Papers 2210.10024, arXiv.org.
    19. Tae-Hwy Lee & Ekaterina Seregina, 2020. "Learning from Forecast Errors: A New Approach to Forecast Combination," Working Papers 202024, University of California at Riverside, Department of Economics.
    20. Kim, Kyongwon, 2022. "On principal graphical models with application to gene network," Computational Statistics & Data Analysis, Elsevier, vol. 166(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:csdana:v:190:y:2024:i:c:s0167947323001834. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/csda .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.