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

Extending bootstrap AMG for clustering of attributed graphs

Author

Listed:
  • D’Ambra, Pasqua
  • Vassilevski, Panayot S.
  • Cutillo, Luisa

Abstract

In this paper we propose a new approach to detect clusters in undirected graphs with attributed vertices. We incorporate structural and attribute similarities between the vertices in an augmented graph by creating additional vertices and edges as proposed in [1, 2]. The augmented graph is then embedded in a Euclidean space associated to its Laplacian and we cluster vertices via a modified K-means algorithm, using a new vector-valued distance in the embedding space. Main novelty of our method, which can be classified as an early fusion method, i.e., a method in which additional information on vertices are fused to the structure information before applying clustering, is the interpretation of attributes as new realizations of graph vertices, which can be dealt with as coordinate vectors in a related Euclidean space. This allows us to extend a scalable generalized spectral clustering procedure which substitutes graph Laplacian eigenvectors with some vectors, named algebraically smooth vectors, obtained by a linear-time complexity Algebraic MultiGrid (AMG) method. We discuss the performance of our proposed clustering method by comparison with recent literature approaches and public available results. Extensive experiments on different types of synthetic datasets and real-world attributed graphs show that our new algorithm, embedding attributes information in the clustering, outperforms structure-only-based methods, when the attributed network has an ambiguous structure. Furthermore, our new method largely outperforms the method which originally proposed the graph augmentation, showing that our embedding strategy and vector-valued distance are very effective in taking advantages from the augmented-graph representation.

Suggested Citation

  • D’Ambra, Pasqua & Vassilevski, Panayot S. & Cutillo, Luisa, 2023. "Extending bootstrap AMG for clustering of attributed graphs," Applied Mathematics and Computation, Elsevier, vol. 447(C).
  • Handle: RePEc:eee:apmaco:v:447:y:2023:i:c:s0096300323000735
    DOI: 10.1016/j.amc.2023.127904
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300323000735
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.amc.2023.127904?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. Christian von Mering & Roland Krause & Berend Snel & Michael Cornell & Stephen G. Oliver & Stanley Fields & Peer Bork, 2002. "Comparative assessment of large-scale data sets of protein–protein interactions," Nature, Nature, vol. 417(6887), pages 399-403, May.
    2. M. E. J. Newman & Aaron Clauset, 2016. "Structure and inference in annotated networks," Nature Communications, Nature, vol. 7(1), pages 1-11, September.
    3. Bothorel, Cecile & Cruz, Juan David & Magnani, Matteo & Micenková, Barbora, 2015. "Clustering attributed graphs: Models, measures and methods," Network Science, Cambridge University Press, vol. 3(3), pages 408-444, September.
    4. Nascimento, Mariá C.V. & de Carvalho, André C.P.L.F., 2011. "Spectral methods for graph clustering - A survey," European Journal of Operational Research, Elsevier, vol. 211(2), pages 221-231, June.
    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. Fengqin Tang & Chunning Wang & Jinxia Su & Yuanyuan Wang, 2020. "Spectral clustering-based community detection using graph distance and node attributes," Computational Statistics, Springer, vol. 35(1), pages 69-94, March.
    2. Zhou, Bin & Yan, Xiao-Yong & Xu, Xiao-Ke & Xu, Xiao-Ting & Wang, Nianxin, 2018. "Evolutionary of online social networks driven by pareto wealth distribution and bidirectional preferential attachment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 507(C), pages 427-434.
    3. Thorben Funke & Till Becker, 2019. "Stochastic block models: A comparison of variants and inference methods," PLOS ONE, Public Library of Science, vol. 14(4), pages 1-40, April.
    4. Jun Liu & Jiangzhou Wang & Binghui Liu, 2020. "Community Detection of Multi-Layer Attributed Networks via Penalized Alternating Factorization," Mathematics, MDPI, vol. 8(2), pages 1-20, February.
    5. Chang, Zhenhai & Yin, Xianjun & Jia, Caiyan & Wang, Xiaoyang, 2018. "Mixture models with entropy regularization for community detection in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 496(C), pages 339-350.
    6. Benati, Stefano & Ponce, Diego & Puerto, Justo & Rodríguez-Chía, Antonio M., 2022. "A branch-and-price procedure for clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 297(3), pages 817-830.
    7. Anna Badalyan & Nicolò Ruggeri & Caterina De Bacco, 2024. "Structure and inference in hypergraphs with node attributes," Nature Communications, Nature, vol. 15(1), pages 1-11, December.
    8. Junhui Cai & Dan Yang & Wu Zhu & Haipeng Shen & Linda Zhao, 2021. "Network regression and supervised centrality estimation," Papers 2111.12921, arXiv.org.
    9. Zhang, Qi & Li, Meizhu, 2022. "A betweenness structural entropy of complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 161(C).
    10. Benati, Stefano & Puerto, Justo & Rodríguez-Chía, Antonio M., 2017. "Clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 261(1), pages 43-53.
    11. Hric, Darko & Kaski, Kimmo & Kivelä, Mikko, 2018. "Stochastic block model reveals maps of citation patterns and their evolution in time," Journal of Informetrics, Elsevier, vol. 12(3), pages 757-783.
    12. Wu, Wei-Wen & Lan, Lawrence W. & Lee, Yu-Ting, 2012. "Exploring the critical pillars and causal relations within the NRI: An innovative approach," European Journal of Operational Research, Elsevier, vol. 218(1), pages 230-238.
    13. Mirko Signorelli & Luisa Cutillo, 2022. "On community structure validation in real networks," Computational Statistics, Springer, vol. 37(3), pages 1165-1183, July.
    14. Haji Gul & Feras Al-Obeidat & Adnan Amin & Fernando Moreira & Kaizhu Huang, 2022. "Hill Climbing-Based Efficient Model for Link Prediction in Undirected Graphs," Mathematics, MDPI, vol. 10(22), pages 1-15, November.
    15. Joseph Crawford & Tijana Milenković, 2018. "ClueNet: Clustering a temporal network based on topological similarity rather than denseness," PLOS ONE, Public Library of Science, vol. 13(5), pages 1-25, May.
    16. Boris Mirkin & Soroosh Shalileh, 2022. "Community Detection in Feature-Rich Networks Using Data Recovery Approach," Journal of Classification, Springer;The Classification Society, vol. 39(3), pages 432-462, November.
    17. Liu, Wei & Chang, Zhenhai & Jia, Caiyan & Zheng, Yimei, 2022. "A generative node-attribute network model for detecting generalized structure and semantics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 588(C).
    18. Yunpeng Zhao & Qing Pan & Chengan Du, 2019. "Logistic regression augmented community detection for network data with application in identifying autism‐related gene pathways," Biometrics, The International Biometric Society, vol. 75(1), pages 222-234, March.
    19. Termeh Shafie & David Schoch, 2021. "Multiplexity analysis of networks using multigraph representations," Statistical Methods & Applications, Springer;Società Italiana di Statistica, vol. 30(5), pages 1425-1444, December.
    20. Mingshuo Nie & Dongming Chen & Dongqi Wang, 2022. "Graph Embedding Method Based on Biased Walking for Link Prediction," Mathematics, MDPI, vol. 10(20), pages 1-13, October.

    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:apmaco:v:447:y:2023:i:c:s0096300323000735. 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: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    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.