A Simple Review of Spatial-based ConvGNN

相关文章：Spatial-based ConvGNN基础

DCNN

论文：[1] Diffusion-convolutional neural networks [2] Diffusion convolutional recurrent neural network Data-driven traffic forecasting

DCNN (Diffusion CNN) 最早由[1]提出

DCNN假设图信号在节点间的转移是一个扩散过程

令$P=D^{-1}A$为归一化转移概率矩阵，$P_{ij}$表示任意时刻信息从节点$i$转移到节点$j$的概率

容易看出矩阵$P$实际上就是邻接矩阵$A$的行归一化形式

扩散过程实际上是一个以$P$为转移概率的马尔科夫链，那么时刻$k$的节点间的扩散概率为$P^k$

于是$k$跳的图扩散卷积定义为

$${\mathbf{H}}^{(k)}=f({\mathbf{W}}^{(k)}\odot {\mathbf{P}}^k\mathbf{X})$$

其中$\odot$表示元素对应相乘

容易发现$H^{(k)}$的计算没有用到上一层表示$H^{(k-1)}$，且和$X$维度相同

DCNN直接对其进行拼接得$H=concat(H^{(1)},\cdots ,H^{(k)})\in R^{N\times k\cdot d}$，并将其输入一个MLP得到最终图节点表示

论文[2]通过如下引理对DCNN进行了改进

扩散过程的平稳分布可以被表示为无限随机游走的加权和

$$\mathcal{P}=\sum _{k=0}^{\mathrm{\infty }}\alpha (1-\alpha {)}^k{P}^k$$

使用有限步数对扩散的平稳分布进行近似，得到的DCNN表达式为

$$\mathbf{H}=\sum _{k=0}^{K}f({\mathbf{P}}^k\mathbf{X}{\mathbf{W}}^{(k)})$$

论文中作者使用这种形式的DCNN结合encoder-decoder结构构建了一个模型用于交通预测，称为DCRNN

RGCN

论文：Modeling Relational Data with Graph Convolutional Networks

RGCN (Relational Graph Convolutional Network) 的motivation是建模关系数据

设图$G=(V,E,R)$，其中$r\in R$为一个关系类型，$(v_i,v_j,r)\in E$是一条关系类型为$r$的边，RGCN的表达式为

$$h_i^{(k+1)}=\sigma (\sum _{r\in \mathcal{R}}\sum _{j\in {\mathcal{N}}_i^r}\frac{1}{c_{i,r}}{W}_r^{(k)}{h}_j^{(k)}+W_0^{(k)}{h}_i^{(k)})$$

其中$Ni^r$\mathrm{是}\mathrm{关}\mathrm{系}$r$\mathrm{下}\mathrm{与}$i$\mathrm{相}\mathrm{邻}\mathrm{的}\mathrm{顶}\mathrm{点}\mathrm{集}\mathrm{合}，$c{i,r}$为归一化常量，可直接设定或作为参数进行学习

论文中RGCN被用于知识图谱的实体分类 (entity classification) 和连接预测 (link prediction)，从更一般的观点来看，RGCN实际上提供了一种处理异构图的通用方法

例如购物网站中，用户关系图和商品相似关系图作为异构的两个图，现在可以通过购买或查看等关系类型的边联系起来，作为一张图处理

GraphSAGE

论文：Inductive Representation Learning on Large Graphs

GraphSAGE (SAmple and aggreGatE) 的motivation是将GCN从transductive扩展到inductive，其表达式为

$${\mathbf{h}}_v^{(k)}=\sigma ({\mathbf{W}}^{(k)}\cdot f_k({\mathbf{h}}_v^{(k-1)},\{{\mathbf{h}}_u^{(k-1)},\mathrm{\forall }u\in S_{\mathcal{N}(v)}\}))$$

其中$S_{N(v)}$是节点$v$邻居节点的随机采样子集合，$f_k(\cdot )$为聚合函数 (aggregation function)

比起GCN，该表达式其实更类似于MPNN的扩展，是标准的Spatial-based

GraphSAGE最特别的地方就是使用固定大小的随机邻居节点集合进行聚合，这样卷积的复杂度就不会随图的增大而变大

聚合函数$f_k$可以是定义在无序向量上的任意函数，例如Mean aggregator、LSTM aggregator、Pooling aggregator等

其中使用Mean aggregator时GraphSAGE就相当于GCN的inductive变体

GAT

论文：Graph attention networks

GAT (Graph attention networks) 将attention思想引入了GNN，其表达式为

$${\mathbf{h}}_v^{(k)}=\sigma (\sum _{u\in \mathcal{N}(v)\cup v}{\alpha }_{vu}^{(k)}{\mathbf{W}}^{(k)}{\mathbf{h}}_u^{(k-1)})$$

该式的含义是使用共享参数的映射$W^{(k)}$对邻接节点分别处理，并通过加权和的方式进行聚合

其中${\alpha }_{vu}$就是相应连接的权重，也即attention权重，其计算方式为

$$\begin{gathered} e_{vu}^{(k)}=LeakyReLU\left({\mathbf{a}}^T\left[{\mathbf{W}}^{(k)}{\mathbf{h}}_v^{(k-1)}||{\mathbf{W}}^{(k)}{\mathbf{h}}_u^{(k-1)}\right]\right) \\ {\alpha }_{vu}^{(k)}=softma{x}_u(e_{vu}^{(k)})=\frac{\exp (e_{vu}^{(k)})}{\sum _{z\in N(v)}\exp (e_{vz}^{(k)})} \end{gathered}$$

其中$[\cdot |\cdot ]$表示concat操作，$\mathbf{a}\in R^{2d}$为可学习的向量

GAT还可以进一步写为multi-head attention的形式

$${\mathbf{h}}_v^{(k)}=conca{t}_{h=1}^H\{\sigma (\sum _{u\in \mathcal{N}(v)\cup v}{\alpha }_{vu}^{(k)}{\mathbf{W}}_l^{(k)}{\mathbf{h}}_u^{(k-1)})\}$$

MoNet

论文：Geometric deep learning on graphs and manifolds using mixture model CNNs

MoNet (mixture model networks) 提出了非欧几何（图、流形等）中的通用spatial-based卷积框架

这里只关注图，设$x$是图中某个节点，$y\in N(x)$是其邻接节点，$u(x,y)$是一个$d$维伪坐标，${\mathbf{w}}_{\mathbf{\Theta }}(u)=(w_1(u),\cdots ,w_J(u))$是一组可学习得权重函数

聚合操作和卷积表示为

$$\begin{gathered} D_j(x)f=\sum _{y\in \mathcal{N}(x)}{w}_j(\mathbf{u}(x,y))f(y),j=1,\dots ,J \\ (f\star g)(x)=\sum _{j=1}^J{g}_j{D}_j(x)f \end{gathered}$$

通过指定不同形式的伪坐标$u(x,y)$和权重核${\mathbf{w}}_{\mathbf{\Theta }}(u)$可以得到不同的图卷积

论文中给出了一种参数化方法

$$\begin{gathered} \mathbf{u}(x,y)=(\frac{1}{\sqrt{deg(x)}},\frac{1}{\sqrt{deg(y)}}{)}^T \\ {w}_j(\mathbf{u})=\exp (-\frac{1}{2}(\mathbf{u}-{\mathit{\mu }}_j{)}^{\mathrm{\top }}{\mathbf{\Sigma }}_j^{-1}(\mathbf{u}-{\mathit{\mu }}_j)) \end{gathered}$$

其中${\mathrm{\Sigma }}_j,{\mu }_j$是可学习的高斯分布协方差矩阵与均值

于是图卷积可表示为

$$h_x^{(k+1)}=\sum _{j=1}^J\sum _{y\in \mathcal{N}(x)}{e}^{-\frac{1}{2}(\tilde{\mathbf{u}}(x,y)-{\mathit{\mu }}_j{)}^{\mathrm{\top }}{\mathbf{\Sigma }}_j^{-1}(\tilde{\mathbf{u}}(x,y)-{\mathit{\mu }}_j)}{h}_y^{(k)}$$

其中$\tilde{\mathbf{u}}(x,y)$是将$\mathbf{u}(x,y)$输入一个非线性全连接层得到的输出