图神经网络社区发现研究综述

doi:10.11896/jsjkx.210500151

摘要/Abstract

摘要： 社区结构是复杂网络中普遍存在的拓扑特性之一,发现社区结构是复杂网络分析的基本任务。社区发现旨在将网络划分为多个子结构,对于理解网络、揭示网络的潜在功能有着重要作用。图神经网络是一种处理图结构数据的模型,具有从图中对数据进行特征提取和表示的优势,已经成为人工智能和大数据领域的重要研究方向。网络数据就是典型的图结构数据,使用图神经网络模型解决社区发现问题,是社区发现研究的一个新方向。首先对GNN模型进行深入探讨,分析GNN社区发现过程,并从重叠社区和非重叠社区这两个方面详细讨论现有GNN社区发现取得的进展以及未来可研究的方向。

关键词: 图神经网络, 社区发现, 深度学习, 重叠社区发现, 非重叠社区发现

Abstract: Community structure is one of the universal topological properties in complex networks,and discovering community structure is the basic task of complex network analysis.The purpose of community detection is to divide the network into several substructures,which plays an important role in understanding the network and revealing its potential functions.Graph Neural Network (GNN) is a model for processing graph structure data,which has the advantage of feature extraction and representation from graph,and has become an important research field of artificial intelligence and big data.Network data is a typical graph structure data.Using graph neural network model to solve the problem of community detection is a new direction of community detection research.In this paper,we first discuss the GNN model,analyze the process of GNN community detection,and discuss the progress of existing GNN community detection and the direction of future research in detail from two aspects of overlapping community and non-overlapping community.

Key words: Graph neural network, Community detection, Deep learning, Overlapping community detection, Non-overlapping community detection

中图分类号:

TP331

宁懿昕, 谢辉, 姜火文. 图神经网络社区发现研究综述[J]. 计算机科学, 2021, 48(11A): 11-16.

NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection[J]. Computer Science, 2021, 48(11A): 11-16.

参考文献

[1]LIU Z Y,ZHOU J.Introduction to Graph Neural Networks[M].Morgan & Claypool,2020:1-3.
[2]HENAFF M,BRUNA J,LECUN Y.DeepConvolutional Net-works on Graph-structured Data[J].arXiv:1506.05163,2015.
[3]BASTINGS J,TITOV I,AZIZ W,et al.GraphConvolutional Encoders for Syntax-aware Neural Machine Translation[C]//Proceedings of the 2017 Conference on EmpiricalMethods in Natural Language Processing.Copenhagen,Denmark,2017:1957-1967.
[4]RHEE S,SEO S,KIM S.Hybrid Approach of Relation Networkand Localized Graph Convolutional Filtering for Breast Cancer Subtype Classification[J].arXiv:1711.05859,2017.
[5]ZHANG Y H,QI P,MANNING C D.Graph Convolution over Pruned Dependency Trees Improves Relation Extraction[C]//Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing.Brussels,Belgium,2018:2205-2215.
[6]GORI M,MONFARDINI G,SCARSELLI F.A New Model for Learning in Graph Domains[C]// IEEE International Joint Conference on Neural Networks.2005:729-734.
[7]SCARSELLI F,GORI M,TSOI A C,et al.The Graph NeuralNetwork Model[J].IEEE Transactions on Neural Networks,2009,20(1):61-80.
[8]BRUNA J,ZAREMBA W,SZLAM A,et al.Spectral Networks and Locally Connected Networks on Graphs[C]//International Conference on Learning Representations (ICLR).2014.
[9]HAMMOND D K,VANDERGHEYNST P,GRIBONAL R.Wavelets on Graphs via Spectral Graph Theory[J].Applied and Computational Harmonic Analysis,2011,30(2):129-150.
[10]KIPF T N,WELLING M.Semi-supervised Classification withGraph Convolutional Networks[C]//International Conference on Learning Representations (ICLR).2017.
[11]LI R,WANG S,ZHU F,et al.Adaptive Graph Convolutional Neural Networks[C]//Proc.of AAAI.2018:3546-3553.
[12]NIEPERT M,AHMED M,KUTZKOV K.Learning Convolutional Neural Networks for Graphs[C]//Proc.of ICML.2016:2014-2023.
[13]HAMILTON W,YINGR,LESKOVEC J.Inductive Representation Learning on Large Graphs[C]//Advances inNeural Information Processing Systems.Long Beach,US,2017:1024-1034.
[14]ATWOOD J,TOWSLEY D.Diffusion-convolutional NeuralNetworks[C]//Proc.of NIPS.2016:1993-2001.
[15]ZHUANG C,MA Q.Dual Graph Convolutional Networks for Graph-based Semi-supervised Classification[C]//Proc.of WWW.2018:499-508.
[16]LUO Z G,JIANG X Z,DING F,et al.New Development ofCommunity Discovery Algorithm in complexnetworks[J].Journal of Defense Science and Technology University,2011,3(1):47-52.
[17]LIU D Y,JIN D,HE D X,et al.Survey of Community Mining in Complex Networks[J].Computer Research and Development,2013,50(10):2140-2154.
[18]CHENG X Q,SHEN H W.Community Structure of Complex Network [J].Complex System and Complexity Science,2011,8(1):57-70.
[19]GRIVAN M,NEWMAN M E J.Community Structure in Social and Biological Networks[J].Proc Natl Acad Sci USA,2002,99(12):7821-7826.
[20]ZHAO W J,ZHANG F B,LIU J L.Research Progress of Community Discovery in Complex Networks[J].Computer Science,2020,47(2):10-20.
[21]LIU F Z,XUE S,WU J,et al.Deep Learning for Community Detection:Progress,Challenges and Opportunities[C]//International Joint Conference on Artificial Intelligence.2020:4981-4987.
[22]XIN X,WANG C K,YING X,et al.Deep Community Detection in Topologically Incomplete Networks[J].Physica A:Statistical Mechanics and its Applocation,2017,469:342-352.
[23]CAO J X,JIN D,YANG L,et al.Incorporating Network Structure with Node Contents for Community Detection on Large Networks using Deep Learning[J].Neurocomputing,2018,297:71-81.
[24]CAO J,JIN D,DANG J W.Autoencoder Based Community Detection with Adaptive Integration of Network Topology and Node Contents[C]//KSEM.2018:184-196.
[25]XU K,HU W H,LESJOVEC J,et al.How Powerful are Graph Neural Networks[C]//ICLR 2019.2019:1-17.
[26]BRUNA J,XIANG L.Community Detection with Graph Neural Networks[J].arXiv:1705.08415,2017.
[27]PETER V,BANDYOPADHYAY S.Self-Expressive GraphNeural Network for Unsupervised Community Detection[J].arXiv:2011.14078,2020.
[28]ZHANG H,ACHARYA D B.Community Detection Clustering via Gumbel Softmax[J].SN Computer Science,2020,1(5):1-11.
[29]ACHARYA D B,ZHANG H.Feature Selection and Extraction for Graph Neural Networks[C]//Proceedings of the 2020 ACM Southeast Conference.2020:252-255.
[30]YANG L,CAO X,HE D,et al.Modularity Based CommunityDetection with Deep Learning[C]//International Joint Confe-rence on Artificial Intelligence.AAAI Press,2016:2252-2258.
[31]CHOONG J J,LIU X,MURATA T.Optimizing VariationalGraph Autoencoder for Community Detection[C]//2019 IEEE International Conference on Big Data (Big Data).IEEE,2019:5353-5358.
[32]SUN J,ZHENG W,ZHANG Q,et al.Graph Neural NetworkEncoding for Community Detection in Attribute Networks[C]//IEEE Transactions on Cybernetics.2020:1-14.
[33]CHEN Z D,LI L S,BRUNA J.Supervised Community Detection with Line Graph Neural Networks[C]//ICLR.2019.
[34]ZHENG Y P,CHEN S Y,ZHANG X N,et al.Heterogeneous-Temporal Graph Convolutional Networks:Make the Community Detection Much Better[J]arXiv:1909.10248,2019.
[35]LU N N,LUO W J,NI L,et al.Extending CDFR for Overlapping Community Detection[C]//Proceedings of the 1st International conference on Data Intelligence and Security.2018:200-206.
[36]LUO W,YAN Z,BU C,et al.Community Detection by Fuzzy Relations[J].IEEE Transactions on Emerging Topics in Computing,2017,1(9):125-134.
[37]SHCHUR O,GUNNEMANN S.Overlapping Community De-tection with Graph Neural Networks[C]//KDD Workshop DLG'19.2019.
[38]TODESCHINI A,MISCOURIDOU X,CARON F.Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities[J].arXiv:1602.02114.
[39]YANG J,LESKOVEC J.Overlapping Community Detection at Scale:A Nonnegative Matrix Factorization Approach[C]//Proceedings of the Sixth ACM International Conference on Web Search and Data Mining.2013.
[40]ZHOU M.Infinite Edge Partition Models for Overlapping Community Detection and Link Prediction[C]//2014 International Conference on Artificial Intelligence and Statistics.2014:1135-1143.
[41]YU Q C,YU Z W,WANG Z,et al.Estimating Posterior Inference Quality of the Relational InfiniteLatent Feature Model for Overlapping Community Detection[J].Frontiers of Computer Science,2020,14(6):1-15.
[42]KOVACS I A,PALOTAI R,SZALAY M S,et al.Community Landscapes:An Integrative Approach to Determine Overlapping Network Module Hierarchy,Identify Key Nodes and Predict Network Dynamics[J].Plos One,2010,5(9):e12528.
[43]JIN D,LIU Z,LI W,et al.Graph Convolutional Networks Meet Markov Random Fields:Semi-Supervised Community Detection in Attribute Networks[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2019:152-159.
[44]LIU D Y,JIN D,HE D X,et al.Survey of Community Mining in Complex Networks[J].Computer Research and Development,2013,50(10):2140-2154.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed