计算机科学 ›› 2020, Vol. 47 ›› Issue (9): 219-225.doi: 10.11896/jsjkx.190900044

• 人工智能 • 上一篇    下一篇

基于深度图卷积胶囊网络的图分类模型

刘海潮1, 王莉2   

  1. 1 太原理工大学软件学院 太原030600
    2 太原理工大学大数据学院 太原030600
  • 收稿日期:2019-09-05 发布日期:2020-09-10
  • 通讯作者: 王莉(wangli@tyut.edu.cn)
  • 作者简介:liuhaichao1028@link.tyut.edu.cn
  • 基金资助:
    国家自然科学基金(61872260);山西省重点研发计划国际合作项目(201703D421013)

Graph Classification Model Based on Capsule Deep Graph Convolutional Neural Network

LIU Hai-chao1, WANG Li2   

  1. 1 College of Software,Taiyuan University of Technology,Taiyuan 030600,China
    2 College of Data Science,Taiyuan University of Technology,Taiyuan 030600,China
  • Received:2019-09-05 Published:2020-09-10
  • About author:LIU Hai-chao,born in 1995,postgra-duate.His main research interests include machine learning,and graph neural network.
    WANG Li,born in 1971,professor,Ph.Dsupervisor,is a member of China Computer Federation.Her main research interests include big data calculation,data mining,and social computing.
  • Supported by:
    National Natural Science Foundation of China (61872260) and Key Research and Development Program International Cooperation Project of Shanxi Province of China (201703D421013).

摘要: 针对提取图表征用于图分类过程中的结构信息提取过程的问题,提出了一种图卷积神经网络与胶囊网络融合的图分类模型。首先,利用图卷积神经网络处理图中的节点信息,迭代以后得到节点表征,表征中蕴含着该节点的子树结构信息;然后,利用Weisfeiler-Lehman图核算法的思想对节点表征的多维度进行排序,得到多视角的图表征;最后,将多视角的图表征整理成胶囊的形式并输入胶囊网络,使用动态路由算法得到更高层次的分类胶囊,进而进行分类。实验结果表明,所提模型在公共数据集上的分类准确度提升了1%~3%,同时具备更强的结构特征提取能力,在少样本情况下的表现比DGCNN更加稳定。

关键词: 图分类, 图表征, 图卷积神经网络, 胶囊网络, Weisfeiler-Lehman图核算法

Abstract: Aiming at the problems of structure information extraction when the extracted graph representation is used for graph classification,a graph classification model based on the fusion of graph convolutional neural network and capsule network is proposed.Firstly,the node information in the graph is processed by the convolutional neural network,and the node representation is obtained after iteration.The sub-tree structure information of the node is contained in the representation.Then,by using the idea of Weisfeiler-Lehman algorithm,the multi-dimensional representations of nodes are sorted to obtain multi-view representations of the graph.Finally,the multi-view graph representations are converted into capsules and input into the capsule network to obtain a higher level of classification capsule by dynamic routing algorithm,then proceed to classification.The experimental results show that the classification accuracy of the proposed model is improved by 1%~3% on the public dataset,and it has stronger structu-ral feature extraction ability.Compared with DGCNN,its performance is more stable in the case of less samples.

Key words: Graph classification, Graph representation, Graph convolutional neural network, Capsule network, Weisfeiler-Lehman graph kernel algorithm

中图分类号: 

  • TP301.6
[1] SCARSELLI F,GORI M,TSOI A C,et al.The graph neuralnetwork model[J].IEEE Transactions on Neural Networks,2009,20(1):61-80.
[2] BRUNA J,ZAREMBA W,SZLAMA,et al.Spectral networksand locally connected networks on graphs[J].arXiv:1312.6203,2013.
[3] DEFFERRARD M,BRESSON X,VANDERGHEYNST P.Con-volutional neural networks on graphs with fast localized spectral filtering[C]//Advances in Neural Information Processing Systems.2016:3844-3852.
[4] KIPF T N,WELLING M.Semi-supervised classification withgraph convolutional networks[J].arXiv:1609.02907,2016.
[5] DUVENAUD D K,MACLAURIN D,IPARRAGUIRRE J,et al.Convolutional networks on graphs for learning molecular fingerprints[C]//Advances in Neural Information Processing Systems.2015:2224-2232.
[6] NIEPERT M,AHMED M,KUTZKOV K.Learning convolu-tional neural networks for graphs[C]//International Conference on Machine Learning.2016:2014-2023.
[7] ZHANG M,CUI Z,NEUMANNM,et al.An end-to-end deep learning architecture for graph classification[C]//Thirty-Se-cond AAAI Conference on Artificial Intelligence.2018.
[8] SABOUR S,FROSST N,HINTONG E.Dynamic routing be-tween capsules[C]//Advances in Neural Information Proces-sing Systems.2017:3856-3866.
[9] BAI L,XU L X,CUI L X,et al.Graph kernel in machine learning:recent works and future developments[J].Journal of Anhui University (Natural Science Edition),2017,41(1):21-28.
[10] HAUSSLER D.Convolution kernels on discrete structures[R].Technical Report UCS-CRL-99-10,UC Santa Cruz,1999.
[11] GÄRTNER T,FLACH P,WROBEL S.On graph kernels:Hardness results and efficient alternatives[M]//Learning Theo-ry and Kernel Machines.Berlin:Springer,2003:129-143.
[12] BORGWARDT K M,KRIEGEL H P.Shortest-path kernels on graphs[C]//Fifth IEEE International Conference on Data Mi-ning (ICDM’05).IEEE,2005.
[13] SHERVASHIDZE N,SCHWEITZER P,LEEUWEN E J,et al.Weisfeiler-lehman graph kernels[J].Journal of Machine Lear-ning Research,2011,12(Sep):2539-2561.
[14] YING Z,YOU J,MORRISC,et al.Hierarchical graph represen-tation learning with differentiable pooling[C]//Advances in Neural Information Processing Systems.2018:4805-4815.
[15] LEE J B,ROSSI R,KONG X.Graph classification using structural attention[C]//Proceedings of the 24th ACM SIGKDD International Conference on KnoWeisfeiler-Lehmanedge Discovery & Data Mining.ACM,2018:1666-1674.
[16] VERMA S,ZHANG Z L.Graph capsule convolutional neural networks[J].arXiv:1805.08090,2018.
[17] GAO H Y,WANG Z Y,JI S W.Large-scale learnable graphconvolutional networks[C]//Proceedings of the 24th ACM SIGKDD International Conference on KnoWeisfeiler-Lehmanedge Discovery & Data Mining.ACM,2018.
[18] ZHOU J,CUI G,ZHANG Z,et al.Graph neural networks:A review of methods and applications[J].arXiv:1812.08434,2018.
[19] SHERVASHIDZE N,VISHWANATHAN S,PETRI T,et al.Efficient graphlet kernels for large graph comparison[C]//AISTATS.2009:488-495.
[20] ATWOOD J,TOWSLEY D.Diffusion-convolutional neural networks[C]//Advances in Neural Information Processing Systems.2016:1993-2001.
[1] 王文刀, 王润泽, 魏鑫磊, 漆云亮, 马义德. 基于堆叠式双向LSTM的心电图自动识别算法[J]. 计算机科学, 2020, 47(7): 118-124.
[2] 张天柱, 邹承明. 使用模糊聚类的胶囊网络在图像分类上的研究[J]. 计算机科学, 2019, 46(12): 279-285.
[3] 樊敏, 王晓锋, 孟小峰. 基于可穿戴设备的心电图自适应分类算法研究[J]. 计算机科学, 2019, 46(12): 292-297.
[4] 王桂娟,印鉴,詹卫许. GC-BES:一种新的基于嵌入集的图分类方法[J]. 计算机科学, 2012, 39(6): 155-158.
[5] 王桂娟,印鉴,詹卫许. 基于类别信息的特征子图选择策略[J]. 计算机科学, 2011, 38(8): 169-170.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 杨羽琦,章国安,金喜龙. 车载自组织网络中基于车辆密度的双簇头路由协议[J]. 计算机科学, 2018, 45(4): 126 -130 .
[9] 施超,谢在鹏,柳晗,吕鑫. 基于稳定匹配的容器部署策略的优化[J]. 计算机科学, 2018, 45(4): 131 -136 .
[10] 韩奎奎,谢在鹏,吕鑫. 一种基于改进遗传算法的雾计算任务调度策略[J]. 计算机科学, 2018, 45(4): 137 -142 .