计算机科学 ›› 2021, Vol. 48 ›› Issue (11A): 11-16.doi: 10.11896/jsjkx.210500151

• 智能计算 • 上一篇    下一篇

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

宁懿昕, 谢辉, 姜火文   

  1. 江西科技师范大学数学与计算机科学学院 南昌330038
  • 出版日期:2021-11-10 发布日期:2021-11-12
  • 通讯作者: 谢辉(huixie@aliyun.com)
  • 作者简介:1509257998@qq.com
  • 基金资助:
    国家自然科学基金项目(71561013,61762044);江西省社会科学研究规划项目(20TQ04);江西省高校人文社会科学研究项目(JC17221,JD18083,JC18109);江西省教育厅科技计划重点项目(GJJ170661)

Survey of Graph Neural Network in Community Detection

NING Yi-xin, XIE Hui, JIANG Huo-wen   

  1. School of Mathematics and Computer Science,Jiangxi Science and Technology Normal University,Nanchang 330038,China
  • Online:2021-11-10 Published:2021-11-12
  • About author:NING Yi-xin,born in 1997.Her main research interests include community detection and graph neural networks.
    XIE Hui,born in 1978,Ph.D,associate professor.His main research interests include data mining and intelligent re-commendation.
  • Supported by:
    National Natural Science Foundation of China (71561013,61762044),Social Science Planning Projects in Jiangxi Province (20TQ04),Fund of Humanities and Social Sciences in Universities of Jiangxi Province (JC17221,JD18083,JC18109) and Key Project of Science & Technology Plan by Education Department of Jiangxi Province(GJJ170661).

摘要: 社区结构是复杂网络中普遍存在的拓扑特性之一,发现社区结构是复杂网络分析的基本任务。社区发现旨在将网络划分为多个子结构,对于理解网络、揭示网络的潜在功能有着重要作用。图神经网络是一种处理图结构数据的模型,具有从图中对数据进行特征提取和表示的优势,已经成为人工智能和大数据领域的重要研究方向。网络数据就是典型的图结构数据,使用图神经网络模型解决社区发现问题,是社区发现研究的一个新方向。首先对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: Community detection, Deep learning, Graph neural network, Non-overlapping community detection, Overlapping community detection

中图分类号: 

  • TP331
[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.
[1] 周芳泉, 成卫青.
基于全局增强图神经网络的序列推荐
Sequence Recommendation Based on Global Enhanced Graph Neural Network
计算机科学, 2022, 49(9): 55-63. https://doi.org/10.11896/jsjkx.210700085
[2] 徐涌鑫, 赵俊峰, 王亚沙, 谢冰, 杨恺.
时序知识图谱表示学习
Temporal Knowledge Graph Representation Learning
计算机科学, 2022, 49(9): 162-171. https://doi.org/10.11896/jsjkx.220500204
[3] 饶志双, 贾真, 张凡, 李天瑞.
基于Key-Value关联记忆网络的知识图谱问答方法
Key-Value Relational Memory Networks for Question Answering over Knowledge Graph
计算机科学, 2022, 49(9): 202-207. https://doi.org/10.11896/jsjkx.220300277
[4] 汤凌韬, 王迪, 张鲁飞, 刘盛云.
基于安全多方计算和差分隐私的联邦学习方案
Federated Learning Scheme Based on Secure Multi-party Computation and Differential Privacy
计算机科学, 2022, 49(9): 297-305. https://doi.org/10.11896/jsjkx.210800108
[5] 孙奇, 吉根林, 张杰.
基于非局部注意力生成对抗网络的视频异常事件检测方法
Non-local Attention Based Generative Adversarial Network for Video Abnormal Event Detection
计算机科学, 2022, 49(8): 172-177. https://doi.org/10.11896/jsjkx.210600061
[6] 闫佳丹, 贾彩燕.
基于双图神经网络信息融合的文本分类方法
Text Classification Method Based on Information Fusion of Dual-graph Neural Network
计算机科学, 2022, 49(8): 230-236. https://doi.org/10.11896/jsjkx.210600042
[7] 王剑, 彭雨琦, 赵宇斐, 杨健.
基于深度学习的社交网络舆情信息抽取方法综述
Survey of Social Network Public Opinion Information Extraction Based on Deep Learning
计算机科学, 2022, 49(8): 279-293. https://doi.org/10.11896/jsjkx.220300099
[8] 郝志荣, 陈龙, 黄嘉成.
面向文本分类的类别区分式通用对抗攻击方法
Class Discriminative Universal Adversarial Attack for Text Classification
计算机科学, 2022, 49(8): 323-329. https://doi.org/10.11896/jsjkx.220200077
[9] 姜梦函, 李邵梅, 郑洪浩, 张建朋.
基于改进位置编码的谣言检测模型
Rumor Detection Model Based on Improved Position Embedding
计算机科学, 2022, 49(8): 330-335. https://doi.org/10.11896/jsjkx.210600046
[10] 侯钰涛, 阿布都克力木·阿布力孜, 哈里旦木·阿布都克里木.
中文预训练模型研究进展
Advances in Chinese Pre-training Models
计算机科学, 2022, 49(7): 148-163. https://doi.org/10.11896/jsjkx.211200018
[11] 周慧, 施皓晨, 屠要峰, 黄圣君.
基于主动采样的深度鲁棒神经网络学习
Robust Deep Neural Network Learning Based on Active Sampling
计算机科学, 2022, 49(7): 164-169. https://doi.org/10.11896/jsjkx.210600044
[12] 苏丹宁, 曹桂涛, 王燕楠, 王宏, 任赫.
小样本雷达辐射源识别的深度学习方法综述
Survey of Deep Learning for Radar Emitter Identification Based on Small Sample
计算机科学, 2022, 49(7): 226-235. https://doi.org/10.11896/jsjkx.210600138
[13] 齐秀秀, 王佳昊, 李文雄, 周帆.
基于概率元学习的矩阵补全预测融合算法
Fusion Algorithm for Matrix Completion Prediction Based on Probabilistic Meta-learning
计算机科学, 2022, 49(7): 18-24. https://doi.org/10.11896/jsjkx.210600126
[14] 杨炳新, 郭艳蓉, 郝世杰, 洪日昌.
基于数据增广和模型集成策略的图神经网络在抑郁症识别上的应用
Application of Graph Neural Network Based on Data Augmentation and Model Ensemble in Depression Recognition
计算机科学, 2022, 49(7): 57-63. https://doi.org/10.11896/jsjkx.210800070
[15] 胡艳羽, 赵龙, 董祥军.
一种用于癌症分类的两阶段深度特征选择提取算法
Two-stage Deep Feature Selection Extraction Algorithm for Cancer Classification
计算机科学, 2022, 49(7): 73-78. https://doi.org/10.11896/jsjkx.210500092
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!