| Computer Technology |
|
|
|
|
| Community detection method based on graph convolutional network via importance sampling |
Xiao-dong CAI( ),Meng WANG,Xiao-xi LIANG,Yun CHEN |
| School of Information and Communication, Guilin University of Electronic Technology, Guilin 541004, China |
|
|
|
Abstract The complex networks were transformed into graph structure data according to the graph theory, so that the convolutional neural networks could be processed efficiently and conveniently. The future of complex networks was extracted by coarsening and pooling for the convolutional layer. Kernels were defined by extending the convolutional operation to images on graph structure data when training the network with stochastic gradient descent. In addition, importance sampling method was designed to change distribution of samples to reduce variance when networks were trained. The experimental results show that, compared with the existing graph convolutional networks, the proposed techniques can obtain better accuracy with lower computational complexity for community detection on the data sets of social networks, citation networks and knowledge graphs. The memory occupation for calculation is greatly reduced and the framework also can be applied to larger complex networks.
|
|
Received: 13 April 2018
Published: 04 March 2019
|
|
|
基于重要性抽样的图卷积社团发现方法
根据图论将复杂网络转化为图结构数据，使卷积神经网络能够高效方便地处理；通过将图像上的卷积操作延伸到图结构数据上来定义卷积核，并通过卷积层对图的粗粒化和池化操作，提取不规则数据复杂网络的特征. 在采用随机梯度下降法训练网络时，设计一种重要性抽样方法改变样本的分布来缩减方差，从而节省梯度计算时间. 实验结果表明，与现有的图卷积网络相比，该方法在社会网络、引文网络、知识图谱数据集中，均能够以较低的计算复杂度获得较好的社团发现准确率；而且能够减少计算时的内存占用，可扩展到更大规模的复杂网络中使用.
关键词：
图卷积,
粗粒化,
社团发现,
重要性抽样,
随机梯度下降
|
|
| [1] |
SUN Y, WANG X, TANG X. Deeply learned face representations are sparse, selective, and robust [C] // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Boston: IEEE, 2015: 2892–2900.
|
|
|
| [2] |
XUE S, YAN Z. Improving latency-controlled BLSTM acoustic models for online speech recognition [C] // Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. New Orleans: IEEE, 2017: 5340–5344.
|
|
|
| [3] |
奚雪峰, 周国栋 面向自然语言处理的深度学习研究[J]. 自动化学报, 2016, 42 (10): 1445- 1465
XI Xue-Feng, ZHOU Guo-Dong A survey on deep learning for natural language processing[J]. Acta Automatica Sinica, 2016, 42 (10): 1445- 1465
|
|
|
| [4] |
FEDERICO M, DAVIDE B, JONATHAN M, et al. Geometric deep learning on graphs and manifolds using mixture model CNNs [C] // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Honolulu: IEEE, 2017: 5425–5434.
|
|
|
| [5] |
MICHAEL M. B, JOAN B, YANN L, et al. Geometric deep learning: going beyond euclidean data[J]. IEEE Signal Processing Magazine, 2017, 34 (4): 18- 42
doi: 10.1109/MSP.2017.2693418
|
|
|
| [6] |
彭静, 廖乐健, 翟英, 等 谱聚类在社团发现中的应用[J]. 北京理工大学学报, 2016, 36 (7): 701- 705
PENG Jing, LIAO Le-jian, ZHAI Ying, et al Spectral clustering for community detection[J]. Transactions of Beijing Institute of Technology, 2016, 36 (7): 701- 705
|
|
|
| [7] |
SHIGA M, TAKIGAWA I, MAMITSUKA H A spectral approach to clustering numerical vectors as nodes in a networks[J]. Pattern Recognition, 2011, 44 (2): 236- 251
doi: 10.1016/j.patcog.2010.08.010
|
|
|
| [8] |
RAGHAVAN U N, ALBERT R, KUMARA S Near linear-time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76 (3): 036106
doi: 10.1103/PhysRevE.76.036106
|
|
|
| [9] |
WANG M, CAI X, ZENG Y, et al. A Community detection algorithm based on jaccard similarity label propagation [C] // Intelligent Data Engineering and Automated Learning. Guilin: IDEAL, 2017: 45–52.
|
|
|
| [10] |
刘大有, 金弟, 何东晓, 等 复杂网络社区挖掘综述[J]. 计算机研究与发展, 2013, 50 (10): 2140- 2154
LIU Da-you, JIN Di, HE Dong-xiao, et al Community ming in complex networks[J]. Journal of Computer Research and Development, 2013, 50 (10): 2140- 2154
doi: 10.7544/issn1000-1239.2013.20120357
|
|
|
| [11] |
DUCH J, ARENAS A Community detection in complex networks using extremal optimization[J]. Physical Review E, 2005, 72 (2): 027104
doi: 10.1103/PhysRevE.72.027104
|
|
|
| [12] |
JOAN B, LI X. Community Detection with graph neural networks. [27 May 2017]. arXiv: 1705.08415v2 [stat.ML].
|
|
|
| [13] |
DUVENAUD D K, MACLAURIN D, IPARRAGUIRRE J , et al. Convolutional networks on graphs for learning molecular fingerprints [C] // Advances in Neural Information Processing Systems. Montreal: NIPS, 2015: 2224–2232.
|
|
|
| [14] |
YANG Z, WILLIAM C, RUSLAN S. Revisiting semi-supervised learning with graph embeddings [C] // Proceedings of the 33nd International Conference on Machine Learning. New York: ICML, 2016: 40–48.
|
|
|
| [15] |
KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks [C] // 5th International Conference on Learning Representations. Toulon: ICLR, 2016. arXiv: 1609.02907.
|
|
|
| [16] |
LI R, WANG S, ZHU F, et al. Adaptive graph convolutional neural networks [C] // The Thirty-Second AAAI Conference on Artificial Intelligence. Louisiana: AAAI, 2018. arXiv: 1801.03226.
|
|
|
| [17] |
DHILLON I S, GUAN Y, KULIS B Weighted graph cuts without eigenvectors a multilevel approach[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29 (11): 1944- 57
doi: 10.1109/TPAMI.2007.1115
|
|
|
| [18] |
Mark Newman network data [DS]. [2017-12-05]. http://www-personal.umich.edu//~mejn/netdata.
|
|
|
| [19] |
HAMILTON W L, YING R, LESKOVEC J. Inductive Representation Learning on Large Graphs [C] // The Thirty-first Annual Conference on Neural Information Processing Systems. Long Beach: NIPS, 2017: 1025–1035.
|
|
|
| [20] |
KINGMA D P, BA J. Adam: a method for stochastic optimization [C] // In International Conference on Learning Representations. San Diego: ICLR, 2015.
|
|
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
