【Graph Neural Networks: A Review of Methods and Applications】

今天读一篇Survey，孙茂松和刘知远老师他们组里写的一篇关于GNN的Survey，算是给自己的CS224W收尾吧。

Introduction

文章的开始就说图是一种可以很好的建模实体和他们之间的关系的数据结构。作为一种非欧式的数据结构，图的应用包括且不仅仅限于节点的分类，关系的预测，以及图中节点的聚类。GNN是一种深度学习的方法，其实GNN在课程上讲得不多，课程之中更多的是一些思想和传统的方法与应用。

GNN是一种新的网络的模型，但是其也逃不掉从他的前辈身上吸取营养，那么我们就看看他是如何从其前辈CNN上面抽取到营养的。CNN大家肯定都非常熟悉了，而CNN之中的一些重要的思想有什么呢？我举几个例子:Local Connection , Weight Sharing , Multi-Layer.这些重要的思想放在图的领域依旧是顺风顺水的。为什么呢？在图之中存在着比图片里面更加明显和重要的Local Connection的性质，而Weight Sharing技术在任何的模型结构之中都可以被用来降低计算的复杂度，对于多层级的结构也是可以在各类的网络之中应用以抽取Hierarchical的结构。只不过有一点就是，CNN是在运行在欧几里得空间的，而图是一种非欧式的结构，所以说我们需要对于CNN做一定程度的泛化和推广，不过现在暂时还是卡住在如何泛化的问题上。

那么除了CNN之外，这么些年的神经网络的发展还给我们带来了什么瑰宝呢？一个非常非常好的东西叫做是Embedding，甚至有人说了一句话叫做“万物皆可Embedding”，也就是将图使用一个低维度的向量表示，DeepWalk算法首次将SkipGram算法使用在了图这种结构之中，之后也引来了各种各样的算法的改进，比如说node2vec还有LINE这类的算法。但是不得不说Embedding也有他们的自己的缺点，第一就是计算的时候很难进行参数的共享，从而造成了计算的低效性，第二，这个问题也是在NLP之中困扰研究者很久的一件事，就是在Embedding的时候仅仅是一次性的获得了一个向量，但是这个向量的泛化能力到底是怎么样呢？可能也确实是还差点意思，这也是后面为什么BERT和ELMO所出现的原因。

而GNN是如何解决上面的这些问题的呢？首先GNN还是吸取了在CNN和RNN这类的模型发展这么久的经验，以层次化建立模型。不过这里几点改进，第一就是假设图之中的节点是无序的，第二，假设边代表了两个节点之间存在关系，因此就可以使得图之中的信息传播。一般来说，GNN之中对于节点的状态的更新是通过周围的节点而实现的。

下面给大家介绍那些模型

Model

Basic Model

GNN的目标也很简单，就是为了去对于每一个节点都给学到一个Hidden State $h_{v} \in R^s$，这个State之中包含了节点的信息以及其边上存在的信息。这时候我们其实还会有一个Output 记做是$o_{v}$,也就是比如说节点的预测这类的东西。如果将$f$记作是一个函数，学名是Local Transition Function,其所作用的对象是各类的节点，以Update他们的状态。而再记一个函数叫做是$g$，其学名叫做是Local Output Function,而他的作用则是将节点映射到output上面，其实看成是两个神经网络就好了。所以就可以定义$h_{v}$和$o_{v}$了

$$h_v = f(x_{v},x_{co[v]} , h_{ne[v]} , x_{ne[v]})$$

其中的$x_{v},x_{co[v]},h_{ne[v]},x_{ne[v]}$则分别代表了节点的特征、节点的边的特征、节点的状态，节点的周围的点的特征。而有了隐态之后我们也就可以处理预测问题了。

$$o_{v} = g(h_{v},x_{v})$$

而如果记$H,O,X,X_{N}$分别是矩阵层面的上述元素，那么就可以写成是一个Compact的形式

$$H = F(H,X)$$

$$O = G(H,X_N)$$

GNN使用的迭代隐态的方法是

$$H^{t+1} = F(H^{t} , X)$$

那么当我们获得了GNN的框架之后，下一个问题就是如何学习到$f,g$的参数了，大家都是学过神经网络的人，我们需要的只有一个玩意就是目标函数，这里的Loss的计算方法可以看成是通过真实的Label与output之间比较

$$loss = \sum_{i=1}^{p} (t_{i} – o_{i} )$$

然后梯度下降就完了，其实上面的如果是分类问题改成BCE，多分类问题改成Softmax配合CE都完全可以。

但是这样的方法还是有一些问题的，第一，循环的更新节点的状态是一个没那么高效的算法，所以可以Design一个多层次结构的GNN获得更加稳定的表示。第二，GNN在更新的时候是使用了相同的矩阵对于所有的元素进行更新的，但是事实上这里可以使用不同的参数更近，也就是说借鉴LSTM或者是GRU之中的参数更新的方法，更新参数的时候可以做一些微调的操作。第三，在这的GNN之中还是不那么可以处理边的数据，比如说，在知识图谱里面是存在着各种不同的性质的边的，那么信息的传递的时候自然也就会出现细微的不同(这里可能可以使用Attention一类的机制来控制信息的传播)

Variants of GNN

Types of Basic Elements

现在来看看还有什么变种的模型的形式呢？比如说有没有对于最新的黑科技的使用呢？当然是有的。下面一一介绍

在原始的GNN之中，Input由那些连接方式是无向图且具有Label信息的节点所组成，也就是最简单的图的形式，但是世界这么大，肯定是有其他的类型的图的，我们稍微先改动一点点，将无向图改成是有向图。

有向图相比于无向图可以给使用者更多的信息，比如说在知识图谱之中，一个边起始于Head，终止于Tail，那么信息在网络之中所传播更新的方式就与两个节点简单的连接不同。有一个算法叫做是DGP就是用两种不同的矩阵分别是$W_p$和$W_c$处理Head节点以及Tail节点。而其对于节点的隐藏状态的更新状态的公式自然也有所改变

$$H^t = \sigma(D_{p}^{-1} A_{p} \sigma(D_c^{-1}A_c H^{t-1} W_c ) W_p)$$

其中的$DA$是经过了归一化之后的邻接矩阵。

那么还有什么其他的方法呢？比如说Heterogeneous Graph，也就是在网络之中是存在着不同的类型的节点的，最简单的处理Heterogeneous Graph的方式就是对于不同的类型的节点使用一个One-Hot的向量进行表示，然后将这个向量表示Concat在原始的向量的后面。还有一个改进的算法叫做GraphInception的利用了一个概念叫做Metapath传递信息，利用Metapath的方法话，可以对于某个中心节点的周围的节点按照种类进行分类进Group之中。而对于每一个Neighbor Group的话，Graph将整个Neighbor视作一个子图，然后在子图层面进行隐层的更新。

上面的都是在节点的层面的考虑问题，那么对于边呢？对于边有什么改进的吗？事实上我们当然是可以对于边进行操作，以保留边上所存在的信息的。第一个方法，就是将原来的图变成一个二分图的形式，在新的二分图之中，原来的边也变成了节点，而原来的图之中的初始节点和结束节点同时连接到二分图另一边的Edge Node代表这两个节点被这条边所连接起来了，而其隐藏状态的表示

$$h_{v}^{t} = \rho ( \frac{1}{|N_v|} \sum_{u\in N_{v}} W_r (r_{v}^{t} \odot h_{u}^{t-1} )+b_r )$$

但是上面的方法在网络特别大的时候，可想而知更新起来会有多么的复杂。那么有没有更加轻量的表达方式呢？聪明的科学家肯定不会把脏活累活都给电脑干。

当然还有一种表达的方式叫做Dynamic Graph，他们拥有静态的图的结构，但是有动态的输入信号，为了捕获这样的结构的信息，有一些模型比如DCRNN，STGCN，Structural-RNN,ST-GCN都是这样的模型，不过具体的运作方式在这个Survey之中也没有讲，自己以后再去补一下这些论文看看吧。

Types of Propagation

刚刚的改进的方法是对于网络之中的节点的类型进行拓展和延伸，但是我们还有其他的改进的方法比如在传播的过程之中进行改进。 在原来的过程之中仅仅是通过简单的Forward的网络连接，但是我们当然可以改进。

比如说使用卷积操作，但是卷积操作往往也被分成了两类，第一类使用了Spectral 方法，第二类使用了Non-Spectral的方法。所谓的Spectral Network是什么意思呢？可以通俗的认为，就是基于特征值的那些方法，而Spectral Approach的卷积核的定义是这么来的

$$g_{\theta}\star x  = Ug_{\theta}(\Lambda)U^T x$$

其中的$U$是归一化的拉普拉斯矩阵的特征向量的矩阵。而$\Lambda$则是特征值的对角矩阵。但是上面的操作看起来表示的清楚明白，事实上却有巨大的计算量，所以要通过特定的方法进行近似处理，下面就一一介绍具体使用Spectral的方法的那些网络结构

ChebNet 听名字就和切比雪夫大哥有关，这里的$g_{\theta}(\Lambda)$可以通过切比雪夫多项式进行近似，也就是说

$$g_{\theta}\star x  = \sum_{k=0}^{K} \theta_{k} T_k (\tilde{L})x$$

这里的$\tilde{L} = \frac{2}{\lambda_{max}} L – I_{N}$.这里的$\lambda_{max}$代指了$L$之中的最大的那个特征值.而什么叫做是切比雪夫多项式(Chebyshev Polynomials)呢？

$$T_k(x) = 2xT_{k-1}(x) – T_{k-2}(x)$$

其中的$T_{0}(x) = 1,T_{1}(x ) = x$，然后不断的迭代下去。

GCN 大名鼎鼎的GCN啊，这里其限制了Layer-Wise的卷积操作为1，以避免过拟合的现象发生。并且其近似的使用$\lambda_{max} \simeq 2$所以等式就可以简化成为

$$g_{\theta}\star x  \simeq \theta_{0}’x +  \theta_{1}'(L – I_{N})x = \theta_{0}’x – \theta_{1}’D^{\frac{1}{2}}AD^{-\frac{1}{2}}x$$

其中存在两个自由变量分别是$\theta_{0}’$和$\theta_{1}’$，如果加上一个限制条件就是$\theta = \theta_{0}’ = -\theta_{1}’$的话，我们就可以写成是下面的这种简单的形式

$$g_{\theta}\star x  \simeq \theta （I_N +D^{-\frac{1}{2}}AD_{-\frac{1}{2}}  )x$$

但是需要注意的是，如果是按照上面的式子计算的话，在计算梯度的时候可能会出现一个问题就是梯度爆炸或者是消失的问题，所以在这里可以采用一个Renormalization Trick，将$I_{N} +D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$转变成为$\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$。其中的$\tilde{A} = A + I_{N}$,而$\tilde{D}_{ii} = \sum_{j}\tilde{A}_{ij}$，所以我们也可以写成是

$$Z = \tilde{D}^{-\frac{1}{2}} \tilde{A}\tilde{D}^{-\frac{1}{2}}X\Theta$$

上面的介绍的这些模型都是使用原本的图的结构来表征节点之间的关系，但是，也可以在这里进行一些改进，比如说Adaptive Graph Convolution Network(AGCN)以学习存在的关系，AGCN学习的是”Residual” Graph Laplacian，所以其可以在处理图结构时更有效(?为什么更有效,和残差连接神经网络一个原理?).还有一种网络叫做Gaussian Process-Based Bayesian Approach(GCP)以解决半监督学习之中的问题。

上面做的都是一些Spectral的方法，换言之，都是基于Laplacian Eigenbasis的方法的。其非常吃模型的结构，也就是说，如果另一个模型的图结构和这个图不同的话，应用起来是问题蛮大的。

所以还有一种方法就是Non-Spectral的方法，其直接在图上面定义卷积，每一次不考虑图的架构而是仅仅考虑周围的节点的性质，这样的一个方法的面临的挑战可能是难以设计出在不同的Size的Neighborhoods的时候依旧可以保持住Local Invariance。

不同的Size的Neighbor用数学的语言描述就是不同的度(Degree),那么我们如果对于每一个度确定的节点都设置一个参数矩阵的话，那么就可以在一定程度上解决这样的问题

$$x = h_{v}^{t-1} + \sum_{i=1}^{|N_{v}|}h_{I}^{t-1}$$

$$h_{v}^{t} = \sigma(xW_{t}^{|N_v|})$$

其中的$W_{t}^{|N_{v}|}$代表的是在第$t$层拥有$|N_{v}|$个节点的权重矩阵。

还有一种方法叫做DCNN，全名叫做是Diffusion-Convolutional Neural Networks被运用于节点的分类任务，可以写成是

$$H = f(W^c  \odot P*X)$$

其中的$X$是一个$N\times F$的向量其中的N是节点的数目，F是特征的数量，而$P^*$则是一个$N\times K\times N$的Tensor，其中包含了$\{P,P^2,\cdots ,P^{K}\}$,$P$被称为是Degree-Normalized Transition Matrix.而如果迁移到对于整个Graph做分类的话，那么就简单的取整体的均值就可以了

$$H  = f(W^c \odot 1_{N}^{T} P^* X/N)$$

还有一种方法叫做是Dual Graph Convolutional Network(DGCN),以同时考虑Graph之中的Local Consistency 和Global的 Consistency，而同时考虑的方法也非常的简单粗暴，就是使用两个卷积网络来处理。其中的第一个神经网络使用的架构是

$$Z = \tilde{D}^{-\frac{1}{2}} \tilde{A}\tilde{D}^{-\frac{1}{2}}X\Theta$$

而第二个网络使用的是

$$H’ = \rho (D_{p}^{-\frac{1}{2}} X_{P} D_{P}^{-\frac{1}{2}}H\Theta )$$

还有很多的方法也都是在处理这样的关系，这就不细说了。但是有一个不得不说，就是GraphSAGE，这个并不是一种方法，可能说更像是一种框架，在这样的一种框架之下，这样的Framework之下，通过Sampling和Aggregating节点的Neighborhood的特征获得节点的特征

$$h_{N_{v}}^{t} = AGGREGATE_{t}(\{h_{u}^{t-1})$$

$$h_{v}^{t} = \sigma(W^t \cdot [h_{v}^{t-1} ||h_{N_{v}}^{t}])$$

而其中的Aggregator可以选择的就非常广了，可以进行MaxPooling,MeanPooling，或者是使用LSTM作为处理手段。

还有一些工作借鉴了LSTM和GRU之中的门控机制来处理图结构之中的问题。比如说有一个网络叫做Gated Graph Neural Network(GGNN),使用了类似Gate Recurrent Units的传播机制

其中的$v$代表的是节点$v$,而$A_v$代表的是$v$的连接矩阵，类似于GRU的更新函数使得其可以从更远的时间步之中更新节点的Hidden State.

LSTM当然也可以使用，但是除了上面的标准类型还有其他的变种类型，比如说Child-Sum Tree LSTM和N-ary Tree LSTM，和标准的LSTM一样，每一个Tree-LSTM之中都有输入i，输出o,记忆层c，隐藏层h，可是与标准的LTSM之中只有一个门不同，在Tree-LSTM之中对于每一个Child节点都存在一个遗忘门。使得节点可以对于不同的子节点进行选择性的遗忘

除了门控机制以外，还有一个非常有意思的机制就是Attention机制也可以被用在Graph之中。比如说非常有名的Self-Attention机制就可以被利用在Graph之中。

$$\alpha_{ij} = \frac{\exp{(LeakyReLU(a^T [Wh_{i} ||Wh_{j} ]))}}{\sum_{k\in N_{i} } \exp(LeakyReLU(a^T [Wh_{i}||Wh_{k}]))}$$

得到了Attention之后，再将其通过一层神经网络之中得到最后的Embedding

$$h_{i}’ = \sigma(\sum_{j \in N_{i}}\alpha_{ij}Wh_{j} )$$

当然在最后一层也可以使用Multi-Head Attention来使得整个的学习过程更加Stabilize.

Training Method

在训练的时候当然还可以进行一些其他的改进的方法，传统的GCN是考虑了图之中的所有的点，然后再处理拉普拉斯矩阵，但是我们也说过了这种方法对于图结构的要求特别大，很难迁移到其他的问题之中，所以有些方法仅仅考虑节点的Neighbor的信息，比如说GraphSAGE模型就是这样处理的，从一个更高层面上面的看的话，GraphSAGE可以看成是在所有的Node之中进行了一个Sampling的操作，Sampling了其周围的节点的信息。那么Sampling的话当然不止一种方式，从Sampling的角度来看的话，PinSage也是一种采样的方法，不过这里的采样是通过一种Random Walk的方法进行的，从一个Target node出发进行随机游走，以寻找到那些最有可能接触的节点。

General Frameworks

Message Passing Neural Networks

有一种被运用在Supervised Learning的新的框架的名字叫做是Message Passing Neural Networks(MPNNs),这个MPNNs Framework并非是按照Spectral与否对于Graph Network进行分类。

在MPNN之中存在两个Phases，一个Phase叫做Message Passing Phase另一个叫做Readout Phase.在第一个阶段之中运行于$T$个时间步之中，在每一个时间步$t$里面存在一个Message Function $M_t$，还有一个Vertex Update Function $U_{t}$.使用Message $m_{v}^{t}$的话，隐藏状态$h_{v}^{t}$的更新函数可以写成是

$$m_{v}^{t+1} = \sum_{\omega \in N_{v}} M_{t}(h_{v}^{t} , h_{w}^{t},e_{vw})$$

$$h_{v}^{t+1} = U_{t}(h_{v}^{t} , m_{v}^{t+1})$$

其中的$e_{vw}$代表了$vw$之间的边的信息，而在Readout的阶段的时候，我们需要使用Readout函数$R$对于整个图都计算一个Feature Vector.

$$\hat{y}  = R(\{h_{v}^{T} | v\in G)$$

通过选择不同的函数，我们可以得到不同的模型，比如说一个模型叫做GGNNs的，函数设置如下

$$M_{t} = A_{e_{vw}}h_{w}^{t}$$

$$U_{t} = GRU(h_v^{t}, m_{v}^{t+1})$$

$$R = \sum_{v\in V} \sigma( i (h_{v}^{T} ,h_{v}^{0} ))\odot(j(h_{v}^{T}))$$

其中的$A$代表的是邻接矩阵。

Non-Local Neural Network

NLNN是为了捕获长距离的依赖关系而设计的网络。Non-Local操作可以看成是一个在CV领域的Non-Local Mean Operation的泛化。具体来说呢，一个Non-Local Operation会计算所有的Position的特征的加权平均作为某一个Position的Response，这里的Position可以看成是时间、空间或者是时空上的位置。所以这个NLNN也可以看成是一种Attention机制的应用。

$$h_{i}’  = \frac{1}{C(h)} \sum_{\forall j}f(h_{i},h_{j})g(h_{j})$$

其中的$i$代表的是输出的Position的Index而$j$是输入的Position的Index.$f()$可以看成是一个权重的计算的过程，而$g()$可以看成是一个特征抽取的函数。所以我们就可以在这里做文章了：

比如说$f(h_{i},h_{j}) = e^{h_{i}^{T} h_{j}}$就是一个选择，这个方法被叫做是Gaussian Method，当然也可以再基于Gaussian方法做一个拓展，即$f(h_{i},h_{j}) = e^{\theta(h_{i})^{T} \phi(h_{j})}$通过增加两个线性变换以加强其表达能力。

或者直接使用$f(h_{i},h_{j}) =h_{i}^{T} h_{j}$也是一个很常见的方法。

Graph Networks

在这样的一个框架，我们首先定义Graph,将其看成是一个三元组$G = (u,H,E)$,这里为了保持记号的一致性，使用$H$代表节点。然后定义一个所谓的GN Block,每一个GN Block之中都包含了三个Updating 函数和三个Aggregation函数

在上面的函数之中的$h_{rk},h_{sk}$分别代表了在第$k$条边之中的Receiver和Sender.模型的更新流程如下

首先$\phi^{e}$应用于$(e_{k} , h_{rk} , h_{sk} , u)$上面得到一个$e_{k}’$,可以看成是通过对于每条边都得到一个Representation,那么获得了每一条边的表示之后，将所有的边记在一个集合$E_{i}’$之中的话，我们认为每一个节点是由其周围的边进行表示的，所以我们再使用$\rho^{e\to h}$得到每一个节点的Representation $\bar{e_{i}’}$,  再使用$\phi^{h}$对于每个节点的参数进行更新得到$h_{i}’$.然后再使用$\rho^{e\to u}$ ，$\rho^{h\to u}$得到Edge和Node的整体表示,最后利用$\phi^{u}$更新Global的States.

 

Comments

本文是对于GNN的发展的脉络的一个非常完整的阐述吧，从GNN的发展上面来看还是可以看见许多的NLP和CV领域之内的成熟的技术被使用了在GNN上面，比如说里面的Cell和连接的函数都广泛的采用了过往的技术以提高性能吧，不过Graph的使用可能还没有广泛的被利用成功吧，更多的还是停留在学术界之中，不过潜力肯定是巨大的，Graph的可拓展性与可定制性都是远超欧几里得空间的吧，甚至以后的非欧式的处理方式会取代欧式的处理方式成为主流，不过这都是后话了吧，自己还是先考虑有没有学上的问题。

Reference

Graph Neural Networks: A Review of Methods and Applications