2019年Philip S. Yu团队的图神经网络综述

使用graph来表示对象之间的复杂关系和依赖关系，然而graph数据的复杂已有的机器学习算法很难处理，所以使用深度学习方法来处理。A Comprehensive Survey on Graph Neural Networks论文回顾图神经网络（GNN）在文本挖掘和机器学习领域的发展，将GNN划分为递归图神经网络、卷积图神经网络、图自编码和时空图神经网络四类。此外还讨论图神经网络跨各种领域的应用、总结开源代码、数据集和图神经网络评价指标。最后给出可能的研究方向。

作者提到基于欧氏距离计算的数据能捕获隐含模式，然而随着应用数量的增加，开始使用graph表示数据，例如，它可以利用用户和商品之间的交互来提高推荐准确率；将化学分子建成graph，生物活性在药物发现中得到鉴定；在引言网络中，通过引用关系建立文章之间的联系，将他们分成不同的类别。然而graph与图像不同，节点无序、尺寸不一、邻居节点数量变化，这增加了graph的计算难度。此外ML算法是基于样本独立性假设的，与graph的构建机理矛盾。

图左：2D卷积。将图像看作graph，就是每个红色点与四周点建立关联，且权重相同

图右：图卷积。邻居节点数量不固定

♕发展历史

1、递归图神经网络（RecGNNs） 1997年起，以迭代的方式并通过传递邻居节点信息来学习目标节点表示，直到稳定点。此类方法计算复杂度高，一些研究者研究如何降低复杂度。如，“Gated graphsequence neural networks，ICLR2015”，“Learning steadystates of iterative algorithms over graphs，ICML2018”.

2、卷积图神经网络（ConvGNNs）分为基于谱方法（最早2013）和基于空间方法（最早2009）

3、图自编码（GAEs)

4、时空图神经网络（STGNNs）

♕图嵌入 vs. 网络嵌入

主要区别：GNN是一组神经网络模型来处理不同任务，网络嵌入涵盖了针对同一任务的各种方法。通过图自编码器框架GNNs能够处理网络嵌入问题。

graph embedding :以端到端的方式处理图关系任务，抽取高阶表示

network embedding: 低维向量表示网络节点，同时保持网络拓扑结构和节点内容信息。因此，任何后续的图形分析任务，如分类、聚类和推荐，都可以使用简单的现成的机器学习算法轻松地执行。网络嵌入还包含非深度学习方法，如矩阵分解和随机游走。

♕图神经网络 vs. 图内核方法

图内核：是解决图分类问题主要技术。使用核函数度量图对之间的相似度，如svm。通过映射函数将图和节点映射到向量空间。采用两两对相似度计算，计算复杂度高

图神经网路：直接根据抽取的图表征执行图分类，比图核方法更有效。通过映射函数将图和节点映射到向量空间。

♕方法定义

图：G=(V,E)，V是节点，E是边

有向图：邻接矩阵是有符号时

时空图：G(t)=(V,E,X(t))

♕方法分类

1. recurrent graph neural networks (RecGNNs)：假设节点和其邻居节点持续变化，直到达到稳态

Graph Neural Network (GNN*2)

Graph Echo State Network(GraphESN)

Gated Graph Neural Network (GGNN)

Stochastic Steady-state Embedding (SSE)

2. convolutional graph neural networks (ConvGNNs):堆多个图卷积层来提取高阶节点表示

（1）Spectral-based ConvGNN

Chebyshev Spectral CNN (ChebNet)

Graph Convolutional Network (GCN)

Adaptive Graph Convolutional Network (AGCN)

Dual Graph Convolutional Network(DGCN)

（2）Spatial-based ConvGNN

Neural Network for Graphs (NN4G)

Contextual Graph Markov Model (CGMM)

Diffusion Convolutional Neural Network (DCNN)

Diffusion Graph Convolution(DGC)

Partition Graph Convolution (PGC)

Message Passing Neural Network (MPNN)

Graph Isomorphism Network (GIN)

Graph Attention Network (GAT)

Gated Attention Network (GAAN)

Mixture Model Network (MoNet)

Large scale Graph Convolutional Network (LGCN)

Improvement in terms of training effificiency：

Fast Learning with Graph Convolutional Network (Fast GCN)

Stochastic Training of Graph Convolutional Networks (StoGCN)

3. graph autoencoders (GAEs)

4. spatial-temporalgraph neural networks (STGNNs)

♕主要数据集

主要包括引用网络（Cora、Citeseer、Pubmed、DBLP(v11)）、生物医学网络(PPI、NCI-1、MUTAG、D&D、PROTEIN、PTC、QM9、Alchemy)、社交网络（Reddit、BlogCatalog）和其他（MNIST、METR-LA、Nell）

♕图神经网络的应用

B. Evaluation & Open-source Implementations

Node Classifification

Graph Classifification

Open-source implementations

C. Practical Applications

Computer vision

Natural language processing

Traffific

Recommender systems

Chemistry

♕未来研究方向

Model depth

Scalability trade-off

Heterogenity

Dynamicity