Computer Science ›› 2020, Vol. 47 ›› Issue (9): 219-225.doi: 10.11896/jsjkx.190900044

• Artificial Intelligence • Previous Articles     Next Articles

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).

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

CLC Number: 

  • 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] ZHANG Zhi-yang, ZHANG Feng-li, CHEN Xue-qin, WANG Rui-jin. Information Cascade Prediction Model Based on Hierarchical Attention [J]. Computer Science, 2020, 47(6): 201-209.
[2] ZHANG Tian-zhu, ZOU Cheng-ming. Study on Image Classification of Capsule Network Using Fuzzy Clustering [J]. Computer Science, 2019, 46(12): 279-285.
[3] . GC-BES:A Novel Graph Classification Approach Based on Embedding Sets [J]. Computer Science, 2012, 39(6): 155-158.
[4] WANG Gui-juan,YIN Jian,ZHAN Wei-xu. Feature Subgraph Selection Strategy Based on Category Information [J]. Computer Science, 2011, 38(8): 169-170.
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] YANG Yu-qi, ZHANG Guo-an and JIN Xi-long. Dual-cluster-head Routing Protocol Based on Vehicle Density in VANETs[J]. Computer Science, 2018, 45(4): 126 -130 .
[9] SHI Chao, XIE Zai-peng, LIU Han and LV Xin. Optimization of Container Deployment Strategy Based on Stable Matching[J]. Computer Science, 2018, 45(4): 131 -136 .
[10] HAN Kui-kui, XIE Zai-peng and LV Xin. Fog Computing Task Scheduling Strategy Based on Improved Genetic Algorithm[J]. Computer Science, 2018, 45(4): 137 -142 .