logo

More info
  • ReceivedMay 16, 2019
  • AcceptedAug 7, 2019
  • PublishedFeb 24, 2020

Abstract

In recent years, with the emergence of massive data, graph structure data that can represent complex relationshipsbetween objects has received more and more attention and has brought great challenges to existing algorithms.As a deep topology information can be revealed, graph neural network models have been widely used in many fields such as communication,life sciences, and finance. This paper reviews the basic models, algorithms, applications and recent developments of existing graph neuralnetworks in recent years, and proposes problems for further research.


Funded by

国家自然科学基金(11631014,11871311)

中央高校基本科研业务费(2018JBM320)


Acknowledgment

本文是在马志明院士于 2018 年 9 月至 10 月组织的“图神经网络” 研讨班上经马志明院士提议并鼓励开始撰写的. 后期, 马志明院士、周川副研究员、唐与聪博士亦提出了许多宝贵意见. 作者在此表示深深感谢.


References

[1] Duvenaud D K, Maclaurin D, Iparraguirre J, et al. Convolutional networks on graphs for learning molecular fingerprints. In: Advances in Neural Information Processing Systems. Montreal: Neural Information Processing Systems Foundation, 2015, 2224--2232. Google Scholar

[2] Miwa M, Bansal M. End-to-end relation extraction using LSTMs on sequences and tree structures.. arXiv Google Scholar

[3] Peng N, Poon H, Quirk C. Cross-sentence $N$-ary relation extraction with graph LSTMs. Trans Assoc Comput Linguist, 2017, 5: 101-115 CrossRef Google Scholar

[4] Garcia V, Bruna J. Few-shot learning with graph neural networks.. arXiv Google Scholar

[5] Wang X, Ye Y, Gupta A. Zero-shot recognition via semantic embeddings and knowledge graphs. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Salt Lake City: IEEE, 2018, 6857--6866. Google Scholar

[6] Zhang M, Chen Y. Link prediction based on graph neural networks.. arXiv Google Scholar

[7] Bojchevski A, Günnemann S. Deep Gaussian embedding of graphs: Unsupervised inductive learning via ranking.. arXiv Google Scholar

[8] Zitnik M, Agrawal M, Leskovec J. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 2018, 34: i457-i466 CrossRef PubMed Google Scholar

[9] Gori M, Monfardini G, Scarselli F. A new model for learning in graph domains. In: Proceedings of the 2005 IEEE International Joint Conference on Neural Networks. Montreal: IEEE, 2005, 729--734. Google Scholar

[10] Scarselli F, Gori M, Tsoi A C, et al. The graph neural network model. IEEE Trans Neural Netw, 2009, 20: 61--80. Google Scholar

[11] Bronstein M M, Bruna J, LeCun Y, et al. Geometric deep learning: Going beyond Euclidean data. IEEE Signal Process Mag, 2017, 34: 18--42. Google Scholar

[12] Zhang Z, Cui P, Zhu W. Deep learning on graphs: A survey.. arXiv Google Scholar

[13] Zhou J, Cui G, Zhang Z, et al. Graph neural networks: A review of methods and applications.. arXiv Google Scholar

[14] Wu Z, Pan S, Chen F, et al. A comprehensive survey on graph neural networks.. arXiv Google Scholar

[15] Bandinelli N, Bianchini M, Scarselli F. Learning long-term dependencies using layered graph neural networks. In: The 2010 International Conference on Neural Networks (IJCNN). Barcelona: IEEE, 2010, 1--8. Google Scholar

[16] Li Y, Tarlow D, Brockschmidt M, et al. Gated graph sequence neural networks.. arXiv Google Scholar

[17] Liao R, Brockschmidt M, Tarlow D, et al. Graph partition neural networks for semi-supervised classification.. arXiv Google Scholar

[18] Johnson D. Learning graphical state transitions. Https://openreview.net/forum?id=HJ0NvFzxl&noteId=HJ0NvFzxl 2017. Google Scholar

[19] Krlevza D, Fertalj K. Graph matching using hierarchical fuzzy graph neural networks. IEEE Trans Fuzzy Systems, 2017, 25: 892--904. Google Scholar

[20] Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs.. arXiv Google Scholar

[21] Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering. In: Advances in Neural Information Processing Systems. Barcelona: Neural Information Processing Systems Foundation, 2016, 3844--3852. Google Scholar

[22] Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks.. arXiv Google Scholar

[23] Levie R, Monti F, Bresson X, et al. Cayleynets: Graph convolutional neural networks with complex rational spectral filters.. arXiv Google Scholar

[24] Wang D, Cui P, Zhu W. Structural deep network embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2016, 1225--1234. Google Scholar

[25] Kipf T N, Welling M. Variational graph auto-encoders.. arXiv Google Scholar

[26] Zhu D, Cui P, Wang D, et al. Deep variational network embedding in wasserstein space. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2018, 2827--2836. Google Scholar

[27] Wang H, Wang J, Wang J, et al. GraphGAN: Graph representation learning with generative adversarial nets.. arXiv Google Scholar

[28] De Cao N, Kipf T. MoIGAN: An implicit generative model for small molecular graphs.. arXiv Google Scholar

[29] Ding M, Tang J, Zhang J. Semi-supervised learning on graphs with generative adversarial nets. In: Proceedings of the 27th ACM International Conference on Information and Knowledge Management. New York: ACM, 2018, 913--922. Google Scholar

[30] You J, Ying R, Ren X, et al. GraphRNN: Generating realistic graphs with deep auto-regressive models. In: International Conference on Machine Learning. Stockholm: International Machine Learning Society, 2018, 5694--5703. Google Scholar

[31] Ma Y, Guo Z, Ren Z, et al. Streaming graph neural networks.. arXiv Google Scholar

[32] Cho K, Merrienboer B, Gulcehre C, et al. Learning phrase representations using RNN encoder-decoder for statistical machine translation.. arXiv Google Scholar

[33] Weston J, Bordes A, Chopra S, et al. Towards AI-complete question answering: A set of prerequisite toy tasks.. arXiv Google Scholar

[34] Rumelhart D E, Hinton G E, Williams R J. Learning representations by back-propagating errors. Nature, 1986, 323: 533-536 CrossRef Google Scholar

[35] Hamrick J B, Allen K R, Bapst V, et al. Relational inductive bias for physical construction in humans and machines.. arXiv Google Scholar

[36] Shuman D I, Narang S K, Frossard P, et al. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Process Mag, 2013, 30: 83--98. Google Scholar

[37] Shuman D I, Ricaud B, Vandergheynst P. Vertex-frequency analysis on graphs. Appl Comput Harmon Anal, 2016, 40: 260--291. Google Scholar

[38] Dhillon I S, Guan Y, Kulis B. Weighted graph cuts without eigenvectors a multilevel approach. IEEE Trans Pattern Anal Mach Intell, 2007, 29: 1944--1957. Google Scholar

[39] Goodfellow I, Bengio Y, Courville A, et al. Deep Learning, Volume 1. Cambridge: MIT Press, 2016. Google Scholar

[40] de Boer P T, Kroese D P, Mannor S. A tutorial on the cross-entropy method. Ann Oper Res, 2005, 134: 19-67 CrossRef Google Scholar

[41] Hinton G E, Zemel R S. Autoencoders, minimum description length and helmholtz free energy. In: Proceedings of the 6th International Conference on Neural Information Processing Systems. San Francisco: Morgan Kaufmann Publishers, 1993, 3--10. Google Scholar

[42] Goodfellow I J, Pouget-Abadie J, Mirza M, et al. Generative adversarial nets. In: Proceedings of the 27th International Conference on Neural Information Processing Systems, vol. 2. Cambridge: MIT Press, 2014, 2672--2680. Google Scholar

[43] Tian F, Gao B, Cui Q, et al. Learning deep representations for graph clustering. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2014, 1293--1299. Google Scholar

[44] Kingma D P, Welling M. Auto-encoding variational Bayes.. arXiv Google Scholar

[45] Baytas I M, Xiao C, Zhang X, et al. Patient subtyping via time-aware LSTM networks. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2017, 65--74. Google Scholar

[46] Di Noi L, Hagenbuchner M, Scarselli F, et al. Web spam detection by probability mapping graphsoms and graph neural networks. In: International Conference on Artificial Neural Networks. New York: Springer, 2010, 372--381. Google Scholar

[47] Yong S L, Hagenbuchner M, Tsoi A C, et al. Document mining using graph neural network. In: International Workshop of the Initiative for the Evaluation of XML Retrieval. New York: Springer, 2006, 458--472. Google Scholar

[48] Chau R, Tsoi A C, Hagenbuchner M, et al. A conceptlink graph for text structure mining. In: Proceedings of the Thirty-Second Australasian Conference on Computer Science, vol. 91. Darlinghurst: Australian Computer Society, 2009, 141--150. Google Scholar

[49] Monfardini G, Di Massa V, Scarselli F, et al. Graph neural networks for object localization. In: Proceedings of the 2006 conference on ECAI 2006: 17th European Conference on Artificial Intelligence August 29--September 1, 2006, Riva del Garda, Italy. Amsterdam: IOS Press, 2006, 665--669. Google Scholar

[50] Di Massa V, Monfardini G, Sarti L, et al. A comparison between recursive neural networks and graph neural networks. In: The 2006 IEEE International Joint Conference on Neural Network Proceedings. Vancouver: IEEE, 2006, 778--785. Google Scholar

[51] Parisot S, Ktena S I, Ferrante E. Disease prediction using graph convolutional networks: Application to autism spectrum disorder and Alzheimer's disease. Med Image Anal, 2018, 48: 117-130 CrossRef PubMed Google Scholar

[52] van den Berg R, Kipf T N, Welling M. Graph convolutional matrix completion.. arXiv Google Scholar

[53] Khalil E, Dai H, Zhang Y, et al. Learning combinatorial optimization algorithms over graphs. In: Advances in Neural Information Processing Systems. Long Beach: Neural Information Processing Systems Foundation, 2017, 6348--6358. Google Scholar

[54] Nowak A, Villar S, Bandeira A S, et al. A note on learning algorithms for quadratic assignment with graph neural networks.. arXiv Google Scholar

[55] Prates M O, Avelar P H, Lemos H, et al. Learning to solve NP-complete problems---a graph neural network for the decision TSP.. arXiv Google Scholar

[56] Selsam D, Lamm M, Bunz B, et al. Learning a sat solver from single-bit supervision.. arXiv Google Scholar

[57] Xu X, Liu C, Feng Q, et al. Neural network-based graph embedding for cross-platform binary code similarity detection. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017, 363--376. Google Scholar

[58] Yu B, Yin H, Zhu Z. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting.. arXiv Google Scholar

[59] Bojchevski A, Shchur O, Zügner D, et al. NetGAN: Generating graphs via random walks.. arXiv Google Scholar

[60] Grover A, Zweig A, Ermon S. Graphite: Iterative generative modeling of graphs.. arXiv Google Scholar

[61] Yadati N, Nitin V, Nimishakavi M, et al. Link prediction in hypergraphs using graph convolutional networks. Https://openreview.net/forum?id=ryeaZhRqFm, 2018. Google Scholar

[62] Simonovsky M, Komodakis N. GraphVAE: Towards generation of small graphs using variational autoencoders. In: International Conference on Artificial Neural Networks. New York: Springer, 2018, 412--422. Google Scholar

[63] Jin W, Barzilay R, Jaakkola T. Junction tree variational autoencoder for molecular graph generation. In: International Conference on Machine Learning. Stockholm: International Machine Learning Society, 2018, 2328--2337. Google Scholar

[64] Baskararaja G J R, Manickavasagam M R S. Subgraph matching using graph neural network. J Intell Learn Syst Appl, 2012, 04: 274-278 CrossRef Google Scholar

[65] Srinivasan A, Muggleton S, King R D, et al. Mutagenesis: ILP experiments in a non-determinate biological domain. In: Proceedings of the 4th International Workshop on Inductive Logic Programming. Bonn: ILP, 1994, 217--232. Google Scholar

[66] Pollastri G, McLysaght A. Porter: A new, accurate server for protein secondary structure prediction. Bioinformatics, 2005, 21: 1719-1720 CrossRef PubMed Google Scholar

[67] Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. J Amer Soc Inf Sci, 2007, 58: 1019-1031 CrossRef Google Scholar

[68] Adamic L A, Adar E. Friends and neighbors on the Web. Soc Networks, 2003, 25: 211-230 CrossRef Google Scholar

[69] Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems. Computer, 2009, 8: 30--37. Google Scholar

[70] Nickel M, Murphy K, Tresp V. A review of relational machine learning for knowledge graphs. Proc IEEE, 2016, 104: 11-33 CrossRef Google Scholar

[71] Oyetunde T, Zhang M, Chen Y. BoostGAPFILL: Improving the fidelity of metabolic network reconstructions through integrated constraint and pattern-based methods. Bioinformatics, 2016, 33: 608-611 CrossRef PubMed Google Scholar

[72] Lü L, Zhou T. Link prediction in complex networks: A survey. Phys A, 2011, 390: 1150-1170 CrossRef Google Scholar

[73] Vinyals O, Fortunato M, Jaitly N. Pointer networks. In: Advances in Neural Information Processing Systems. Montreal: Neural Information Processing Systems Foundation, 2015, 2692--2700. Google Scholar

[74] Wang T, Liao R, Ba J, et al. NerveNet: Learning structured policy with graph neural networks. Https://openreview.net/forum?id=S1sqHMZCb, 2018. Google Scholar

[75] He K, Zhang X, Ren S, et al. Deep residual learning for image recognition. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Singapore: IEEE, 2016, 770--778. Google Scholar

[76] Zhou J, Cui G, Zhang Z, et al. Graph neural networks: A review of methods and applications.. arXiv Google Scholar

[77] Li Q, Han Z, Wu X M. Deeper insights into graph convolutional networks for semi-supervised learning.. arXiv Google Scholar

[78] Szegedy C, Zaremba W, Sutskever I, et al. Intriguing properties of neural networks.. arXiv Google Scholar

[79] Zügner D, Akbarnejad A, Günnemann S. Adversarial attacks on neural networks for graph data. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2018, 2847--2856. Google Scholar

[80] Zhang Y, Pal S, Coates M, et al. Bayesian graph convolutional neural networks for semi-supervised classification.. arXiv Google Scholar

[81] Dai H, Li H, Tian T, et al. Adversarial attack on graph structured data. In: International Conference on Machine Learning. Stockholm: International Machine Learning Society, 2018, 1123--1132. Google Scholar

[82] Sun L, Wang J, Yu P S, et al. Adversarial attack and defense on graph data: A survey.. arXiv Google Scholar

[83] Chen J, Zhu J, Song L. Stochastic training of graph convolutional networks with variance reduction. In: International Conference on Machine Learning. Stockholm: International Machine Learning Society, 2018, 941--949. Google Scholar

[84] Chen J, Ma T, Xiao C. FastGCN: Fast learning with graph convolutional networks via importance sampling.. arXiv Google Scholar

[85] Hamilton W, Ying Z, Leskovec J. Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems. Long Beach: Neural Information Processing Systems Foundation, 2017, 1024--1034. Google Scholar

[86] Gao H, Wang Z, Ji S. Large-scale learnable graph convolutional networks. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2018, 1416--1424. Google Scholar

  • Figure 1

  • Figure 2

  • Figure 3

  • Figure 4

  • Table 1   模型分类
    分类模型
    空间方法GoriGNN [9,10]、 LGNN [15]、 GGS-NN [16]、 GPNN [17]、 GGT-NN [18]、 FGNN [19]
    谱方法 SpectralGCN [20]、 ChebNets [21]、 GCN [22]、 CayleyNets [23]
    图生成 基于自编码器: SDNE [24]、 VGAE [25]、 DVNE [26]
    基于生成对抗网络: GraphGAN [27]、 MolGAN [28]、 GraphSGAN [29]
    其他生成方法: GraphRNN [30]、 DGNN [31]
  • Table 2   应用分类
    分类应用
    节点分类子图匹配、 突变检测、 网页排序 [10]、 团定位、 二级蛋白质结构预测 [15]
    网络垃圾邮件分类 [46]、 bAbI、 规则发现 [16,18]、 文本挖掘 [47,48]
    目标定位 [49]、 图像分类 [50]、 规则发现 [18]、 引文网络 [17,22]、 疾病预测 [51]
    Euclid 问题、 文本分类 [21]、 知识图谱分类 [22]、 社团探测 [23]、 矩阵补全 [23,52]
    组合优化(TSP 问题、 SAT 问题) [53-56]、 相近二进制码检测 [57]、 交通预测 [58]
    链路预测引文网络 [59,60]、 信息传播预测 [6]、 超图链路预测 [61]
    图生成小规模图生成 [62]、 化学分子图自动生成 [63]
    社交网络、 2D-网格图、蛋白质结构预测 [30]、 生成特定化学特性的分子 [28]

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号