计算机科学 ›› 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: Graph neural network, Community detection, Deep learning, Overlapping community detection, Non-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] 董晓梅, 王蕊, 邹欣开. 面向推荐应用的差分隐私方案综述[J]. 计算机科学, 2021, 48(9): 21-35.
[2] 周新民, 胡宜桂, 刘文洁, 孙荣俊. 基于多模态多层级数据融合方法的城市功能识别研究[J]. 计算机科学, 2021, 48(9): 50-58.
[3] 钱梦薇, 过弋. 融合偏置深度学习的距离分解Top-N推荐算法[J]. 计算机科学, 2021, 48(9): 103-109.
[4] 徐涛, 田崇阳, 刘才华. 基于深度学习的人群异常行为检测综述[J]. 计算机科学, 2021, 48(9): 125-134.
[5] 张新峰, 宋博. 一种基于改进三元组损失和特征融合的行人重识别方法[J]. 计算机科学, 2021, 48(9): 146-152.
[6] 林椹尠, 张梦凯, 吴成茂, 郑兴宁. 利用生成对抗网络的人脸图像分步补全法[J]. 计算机科学, 2021, 48(9): 174-180.
[7] 黄晓生, 徐静. 基于PCANet的非下采样剪切波域多聚焦图像融合[J]. 计算机科学, 2021, 48(9): 181-186.
[8] 田野, 陈宏巍, 王法胜, 陈兴文. 室内移动机器人的SLAM算法综述[J]. 计算机科学, 2021, 48(9): 223-234.
[9] 陈湘涛, 赵美杰, 杨梅. 基于子图结构的局部社区发现算法[J]. 计算机科学, 2021, 48(9): 244-250.
[10] 谢良旭, 李峰, 谢建平, 许晓军. 基于融合神经网络模型的药物分子性质预测[J]. 计算机科学, 2021, 48(9): 251-256.
[11] 冯霞, 胡志毅, 刘才华. 跨模态检索研究进展综述[J]. 计算机科学, 2021, 48(8): 13-23.
[12] 王立梅, 朱旭光, 汪德嘉, 张勇, 邢春晓. 基于深度学习的民事案件判决结果分类方法研究[J]. 计算机科学, 2021, 48(8): 80-85.
[13] 郭琳, 李晨, 陈晨, 赵睿, 范仕霖, 徐星雨. 基于通道注意递归残差网络的图像超分辨率重建[J]. 计算机科学, 2021, 48(8): 139-144.
[14] 刘帅, 芮挺, 胡育成, 杨成松, 王东. 基于深度学习SuperGlue算法的单目视觉里程计[J]. 计算机科学, 2021, 48(8): 157-161.
[15] 王施云, 杨帆. 基于U-Net特征融合优化策略的遥感影像语义分割方法[J]. 计算机科学, 2021, 48(8): 162-168.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 秦李,杨子龙,黄曙光. 复杂网络的节点重要性综合评价[J]. 计算机科学, 2015, 42(2): 60 -64 .
[2] 敬颉, 陈潭, 杜文丽, 刘志康, 尹皓. 自动驾驶场景中增强深度学习的时空特征提取方法[J]. 计算机科学, 2019, 46(11A): 1 -4 .
[3] 韩雪娟, 李国东, 王思秀. 基于Logistic和超混沌结合的加密算法[J]. 计算机科学, 2019, 46(11A): 477 -482 .
[4] 朱凯, 毋国庆, 袁梦霆. 关于同步部分规约的有限自动机的优化问题的近似难度[J]. 计算机科学, 2020, 47(5): 14 -21 .
[5] 刘江, 周鸿昊. 一种布尔公式的代数逻辑约化新方法[J]. 计算机科学, 2020, 47(5): 32 -37 .
[6] 宋勃升, 程玉. 带膜分裂和促进剂的通讯膜系统求解QSAT问题[J]. 计算机科学, 2020, 47(5): 38 -42 .
[7] 胡宇佳, 甘伟, 朱敏. 基于多特征融合的增强子-启动子相互作用预测综述[J]. 计算机科学, 2020, 47(5): 64 -71 .
[8] 王青松, 姜富山, 李菲. 大数据环境下基于关联规则的多标签学习算法[J]. 计算机科学, 2020, 47(5): 90 -95 .
[9] 向伟, 王新维. 基于多类邻域三支决策模型的不平衡数据分类[J]. 计算机科学, 2020, 47(5): 103 -109 .
[10] 王军浩, 闫德勤, 刘德山, 邢钰佳. 融合极端学习机的判别性分析字典学习算法[J]. 计算机科学, 2020, 47(5): 137 -143 .