基于图增强和图神经网络的层次社区发现方法

Hierarchical community detection method based onenhanced graph and graph neural networks

[目的]现有的多分辨率层次社区发现方法需要搜索分辨率参数得到特定层次的社区划分,且无法利用网络拓扑与节点属性之间的关联获取社区结构信息.为解决这些限制,本文提出一种基于图增强和图神经网络的层次社区发现方法HCEG.[方法]首先在图增强过程中对原始网络进行重构,使得构建的初始社区种子能涵括节点属性和拓扑信息,然后对初始种子社区集进行合并,再采用基于图神经网络的方法进行拓展,以搜寻网络中不同层次的社区划分.[结果]与其他SOTA方法相比,所提出的HCEG方法可以准确地找到不同类型真实网络中的分层社区结构,并可在不同规模的真实网络中可以获得良好的社区发现性能.[结论]在社交网络、引文网络、网页超链接网络等真实数据集上的一系列实验,验证了HCEG方法的可行性和有效性.

[Objective]As an effective way to analyze structures and characteristics of a complex network,community detection helps people understand properties and evolution of networks.However,communities in complex networks often contain hierarchical structures,and most existing multi-resolution community detection methods need to search for appropriate resolution parameters to obtain hierarchical community divisions and cannot analyze the association between network topology and node attributes to obtain deep-level community structure information.To address these limitations,we have developed a community detection method that can leverage richer network information while achieving specific accuracy in hierarchical community segmentation.[Methods]In this paper,we propose a hierarchical community detection method(HCEG),based on enhanced graph and Graph Neural Networks(GNN).Specifically,HCEG first utilizes a variational graph autoencoder to reconstruct the network,enabling the link structure of the reconstructed graph to reflect both the topology structure and node information of the original network.Then,by searching for the largest k-plex subgraph in the reconstructed graph,the initial community center is constructed,and features in the attribute network are incorporated into the community generation and graph learning process.Finally,based on the attribute similarity of community members,candidate seed communities are merged and divided into different levels of communities through a GNN model.[Results]Several experiments are conducted to validate the feasibility and effectiveness of the HCEG in hierarchical community detection tasks on multiple attribute networks including user relationship network,scientific publication network,and webpage hyperlink network.Overall experimental results show that the proposed HCEG method can accurately find hierarchical community structures in different types of real networks when compared to other SOTA methods,and HCEG can achieve good community discovery performance in real networks of different sizes.We further investigate the impact of graph enhancement strategies on the community detection performance of the HCEG by varying the proportion of edge augmentation and the type of graph autoencoder.Additionally,we study whether or not graph enhancement strategies should be used.Experimental results on different datasets and levels show that the performance of the HCEG(OG)model(without graph enhancement strategies)is significantly inferior to those of other models,indicating that graph enhancement strategies can effectively improve the performance of the HCEG in community detection tasks.In the process of community expansion,the HCEG method uses an improved GraphSAGE algorithm to match suitable seed communities for the remaining node members in the network.To study the effectiveness of the improved GraphSAGE algorithm in community expansion,we set up a multilayer perceptron(MLP)as a community expansion strategy and compared it with the GraphSAGE.Experimental results show that the HCEG(VGAE+GS)model using the improved GraphSAGE algorithm as a community expansion strategy outperforms the HCEG(VGAE+MLP)model.For the identification of the community categories of nodes in the network,it is not conducive to use only the multilayer perceptron and discard the network topology information.[Conclusions]In this paper,we propose a method for hierarchical community detection based on graph enhancement and graph neural networks,called HCEG.It addresses problems of existing hierarchical community detection methods that cannot efficiently obtain community structures at specific levels and nor can readily leverage attribute network information.By designing a graph enhancement process,the algorithm can integrate the attribute descriptions of node members when we construct initial seed communities,and further merge and expand the obtained initial seed community set to achieve rapid division of communities at various levels.Experimental results on seven real-world datasets show that,compared to other methods,HCEG can fully utilize network information to mine community structures at specific levels in the network.