AComprehensiveSurveyonGraphNeuralNetwork

• 论文地址&＃xff1a;https://ieeexplore.ieee.org/stamp/stamp.jsp?tp&＃61;&arnumber&＃61;9046288
• 来源&＃xff1a;IEEE Transactions on Neural Networks and Learning Systems, 2020
• 作者&＃xff1a;Zonghan Wu, Shirui Pan et.al
• 关键词&＃xff1a;Deep Learning, graph neural networks, graph convolutional networks, graph representation learning, graph autoencoders

1. 前言

该论文对今年来图神经网络的发展和应用进行了全面的总结&＃xff0c;包括对最近的GNNs进行分类、GNNs在不同领域内的应用、开源的代码和基准数据集、GNNs的模型评估以及GNN未来可能的发展方向。

2. GNNs分类

该论文将GNNs分为四大类&＃xff1a;recurrent gnns RecGNNs&＃xff09;、convolutional gnns&＃xff08;ConvGNNs&＃xff09;、graph autoencoders&＃xff08;GAEs&＃xff09;、spatial-temporal gnns&＃xff08;STGNNs&＃xff09;。

2.1 RecGNNs

大多是GNNs较为早期的工作&＃xff0c;目的是通过循环的神经结构来学习结点/图的表征&＃xff0c;结点间一轮一轮地交换信息就相当于循环地过程。\cite{li2015gated}就是其中的一种。RecGNN的结点表征更新如下&＃xff1a;
hv(t)&＃61;∑u∈N(v)f(Xv,X(v,u)e,hu(t−1))\boldsymbol{h}^{(t)}_v &＃61; \sum_{u \in N(v)} f(\boldsymbol{X}_v, \boldsymbol{X}^{\boldsymbol{e}}_{(v,u)}, \boldsymbol{h}^{(t-1)}_u) hv(t)​&＃61;u∈N(v)∑​f(Xv​,X(v,u)e​,hu(t−1)​)
其中$f$是recurrent function&＃xff0c;该函数应该是一个压缩映射&＃xff08;可以用NN来实现&＃xff09;&＃xff0c;能够将输入映射到一个更紧凑的空间中。本质上&＃xff0c;RecGNNs是基于信息传播的模型的&＃xff0c;通过一轮轮的传播来更新表征。

2.2 ConvGNNs

现在最常见的GNNs — 图卷积神经网络。ConvGNNs和RecGNNs很像&＃xff0c;但是有一个很明显的区别 — ConvGNNs通过不同的层来完成结点之间信息的交换&＃xff0c;且层所代表的映射可以不是压缩映射&＃xff0c;且ConvGNNs的层一般都是不一样的&＃xff0c;而RecGNNs中的$f$通常都是同一个函数。二者的对比如下图所示。

在这四种GNNs中&＃xff0c;ConvGNNs算是发展得最迅猛、相关工作最多的一类了。ConvGNNs又可以分为两类&＃xff1a;Spectral-based ConvGNNs和Spatial-based ConvGNNs。

Spectral-based的方法从图信号处理的角度定义了图卷积。Spectral-based默认graph是无向的&＃xff0c;spectral下的图卷积需要对图的Laplacian矩阵进行谱分解L&＃61;UΛUT\mathbf{L}&＃61;\mathbf{U} \Lambda \mathbf{U}^{T}L&＃61;UΛUT&＃xff0c;对graph signal进行卷积需要进行\textit{graph Fourier transform}&＃xff0c;即F(x)&＃61;UTx\mathscr{F}(\mathbf{x})&＃61;\mathbf{U}^{T} \mathbf{x}F(x)&＃61;UTx&＃xff0c;其中$\mathbf{x}$为输入的graph signal。图傅里叶变换能够将graph signal变换到由$\mathbf{U}$定义的正交空间中。那么给定一个filter&＃xff08;和图像处理领域的滤波器很像&＃xff09;$\mathbf{g}$&＃xff0c;那么对一个graph signal的卷积定义如下&＃xff1a;
x∗Gg&＃61;F−1(F(x)⊙F(g))&＃61;U(UTx⊙UTg)\begin{aligned} \mathbf{x} *_{G} \mathbf{g} &&＃61;\mathscr{F}^{-1}(\mathscr{F}(\mathbf{x}) \odot \mathscr{F}(\mathbf{g})) \\ &&＃61;\mathbf{U}\left(\mathbf{U}^{T} \mathbf{x} \odot \mathbf{U}^{T} \mathbf{g}\right) \end{aligned} x∗G​g​&＃61;F−1(F(x)⊙F(g))&＃61;U(UTx⊙UTg)​
那么Spectral CNN的定义如下&＃xff0c;其中Θi,j(k)\Theta_{i, j}^{(k)}Θi,j(k)​是需要学习的滤波器&＃xff1a;
H:,j(k)&＃61;σ(∑i&＃61;1fk−1UΘi,j(k)UTH:,i(k−1))(j&＃61;1,2,⋯,fk)\mathbf{H}_{:, j}^{(k)}&＃61;\sigma\left(\sum_{i&＃61;1}^{f_{k-1}} \mathbf{U} \Theta_{i, j}^{(k)} \mathbf{U}^{T} \mathbf{H}_{:, i}^{(k-1)}\right) \quad\left(j&＃61;1,2, \cdots, f_{k}\right) H:,j(k)​&＃61;σ(i&＃61;1∑fk−1​​UΘi,j(k)​UTH:,i(k−1)​)(j&＃61;1,2,⋯,fk​)
spectral-based的图卷积有很坚实的数学基础&＃xff0c;但也存在一些局限性&＃xff1a;

• 不同的结点排列会产生不同的谱分解 — 不是结点排列无关的
• 学习到的滤波器是领域相关的 — 难以应用到其他领域
• 矩阵分解计算复杂 — 难以应用到large scale graph上

Spatial-based即空域的图卷积&＃xff0c;是目前的主流。空域的图卷积与图像中的CNN很像。过程&＃xff1a;将邻居结点的信息汇聚后&＃xff0c;再通过某个函数将结点自身的信息与汇聚后的邻居信息结合起来&＃xff0c;与spectral-based的方法相比更直观。在空域卷积的基础上还诞生了图注意力网络 Graph Attention Network。与基础的空域卷积相比&＃xff0c;结点与其邻居结点间的权重改由注意力替代。二者的比较如下图所示&＃xff1a;

除了GAT还出现了与图像领域中类似的操作&＃xff0c;如Graph Pooling&＃xff0c;功能也与图像领域的池化操作类似 — 降低图的规模/从结点表征矩阵产生图表征&＃xff08;Readout&＃xff09;。

2.3 GAEs

图自编码器 — encoder将graph的结点映射到隐空间中&＃xff0c;decoder将隐空间中的图还原/重建。GAEs可以用来学习结点的表征以及生成图。一个现有的GAEs的一个统计表如下图所示。

使用GAEs来生成图可以分为两类&＃xff1a;Sequential — 逐步地增减结点/边&＃xff0c;Global — 一次性生成整个graph。

2.4 STGNNs

时空地图神经网络&＃xff0c;这种GNNs主要用在dynamic graphs上 — 捕捉时间序列地特征/分布&＃xff0c;序列与graph的联合/边缘分布&＃xff0c;graph在时间、空间上的关系。STGNNs的任务可以是预测预测结点的值/标签或者graph的便签 — 当然是结合时间的。常见的应用场景包括流式的图数据、交通数据&＃xff08;如交通中的流量、速度等数据&＃xff09;等。STGNNs目前主要由两个发展方向&＃xff1a;RNN-based和CNN-based。

RNN-based方法会单独处理每一个时刻的图数据&＃xff0c;并作为输入流入下一个时刻的处理步骤。有些方法会将结点和边分开来处理 — 分别输入RNN-based处理单元中。CNN-based方法以非循环的方式来处理&＃xff0c;RNN-based和CNN-based有点像RecGNNs和ConvGNNs&＃xff0c;CNN-based方法通过堆叠多层网络来处理dynamic graph。

3. GNNs应用

3.1 Computer Vision

包括场景图生成、点云数据分类、动作识别。在场景图中&＃xff0c;GNNs可以帮助识别对象之间的语义关系&＃xff0c;与之相反的是场景图的生成&＃xff0c;将自然语言描述的场景生成为场景图。

3.2 Natural Language Processing

GNNs可以借助文本中句子/词之间的关系来对文本进行分类&＃xff0c;除此之外&＃xff0c;在NLP领域还有很多自然的grpah-like数据&＃xff0c;如语法依存树。同时也可以基于语义图&＃xff08;semantic graph&＃xff09;来生成文本或者反过来。

3.3 Traffic

例如动态预测道路的可行驶速度、流量等&＃xff0c;这通常与STGNNs联系起来。通常将交通网络看作时空图&＃xff0c;其中的结点为安装在路上的传感器、边表示传感器之间的距离&＃xff0c;这样每个结点在一定的时间区间内都有自己的流速。

3.4 Recommender system

Graph-based的推荐系统通常将用户、商品视作结点&＃xff0c;通过利用结点之间的关系以及与相关的信息融合起来进行推荐。推荐系统的一个关键点&＃xff1a;针对一个用户&＃xff0c;给出每个商品对其的重要性排序/分数&＃xff0c;这也可以转化为一个链接预测问题 — 预测用户和商品之间的链接。

3.5 Chemistry

在生物/化学/生物信息领域&＃xff0c;通常利用GNNs来研究分子/化合物/药物的结构 — 这些东西也天然地具有graph结构。

3.6 Others

除了上述的几个主要的应用领域&＃xff0c;还存在一些比较小众/还未广泛研究的领域&＃xff0c;例如程序验证、程序推理、社会影响力预测、对抗攻击防御、异常检测、脑网络研究等。

4. GNNs模型评估

在GNNs中有几个主要的任务&＃xff1a;结点分类、图分类、链接预测&＃xff08;我自己补充的&＃xff09;。

5. 常用数据集

常见的数据如下图所示&＃xff1a;

6. 未来发展方向

6.1 Model Depth

就目前的情况来看&＃xff0c;GNNs的模型都比较浅&＃xff0c;与CNN模型动则数十层的模型相比&＃xff0c;GNNs的模型层数都比较少。当GNN中层数较多时&＃xff0c;基本上每个结点的信息都已经被传播到了图中其余的结点 — 通常图的最短路径会在6跳左右/六度分隔&＃xff0c;这也导致当层数一多&＃xff0c;图中结点的表征就会趋于一致&＃xff0c;这反而使得结点的表征不具有区分性。\tbc{red}{如何加深GNNs或者什么情况下需要深度的GNNs是一个很值得研究的问题}。

6.2 Scalability trade-off

伸缩性权衡。GNNs的可伸缩性是以破坏图的完整性为代价的。在现有的GNNs中&＃xff0c;通常会有ZPooling和Coarsening操作来降低节点特征的维度或者图的规模&＃xff0c;但是这些操作都或多或少的丢失了一部分信息。如何设计一个破坏图数据完整性的GNN或者如何权衡完整性和可行性是一个很值得研究的问题。

6.3 Hetergenity

GNNs在异质图数据上的应用。目前大多数的GNNs处理的是同质的图数据 — 结点都为同一类型或者只有一种类型&＃xff0c;边也只有一种类型&＃xff0c;但是还有很多数据是异质的 — 结点/边的类型是多样的&＃xff0c;以及结点/边的输入形式都是不一样的&＃xff0c;例如结点/边为文本/图像等&＃xff0c;这可以视作现在的多模态融合问题&＃xff0c;相当于以GNNs来进行多模态数据融合。

6.4 Dynamicity

虽然已经有STGNNs来处理随时间变化的图数据&＃xff0c;但是大部分都没有dynamic spatioal relations&＃xff08;这里我不太理解&＃xff09;。不过确实需要设计更好的处理动态的图数据、流式的图数据&＃xff08;流式的数据处理是一个很有意思的问题&＃xff09;。

这篇综述是2019年发表的&＃xff0c;虽然在2020年已经出现了很多新的关于GNNs的工作&＃xff0c;一些工作也与文中谈的一些问题重叠了&＃xff0c;但是这篇综述依然是一片很全面、详细的对GNNs今年来的工作的总结&＃xff0c;提出的问题也很具有参考性&＃xff0c;是一篇非常棒的综述&＃xff01;

欢迎访问我的个人博客~~~