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}^{\infty}\alpha(1-\alpha)^kP^k$$

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

$$\mathbf{H}=\sum_{k=0}^Kf(\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\left(\sum_{r\in\mathcal{R}}\sum_{j\in\mathcal{N}_i^r}\frac1{c_{i,r}}W_r^{(k)}h_j^{(k)}+W_0^{(k)}h_i^{(k)}\right)$$

其中$Ni^r$是关系$r$下与$i$相邻的顶点集合，$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)},\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权重，其计算方式为

$$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)}=softmax_u(e_{vu}^{(k)})=\frac{\exp(e_{vu}^{(k)})}{\sum_{z\in N(v)}\exp(e_{vz}^{(k)})}$$

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

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

$$\mathbf{h}_v^{(k)}=concat_{h=1}^H\left\{\sigma(\sum_{u\in\mathcal{N}(v)\cup v}\alpha_{vu}^{(k)}\mathbf{W}^{(k)}_l\mathbf{h}_u^{(k-1)})\right\}$$

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_{\Theta}}(u)=(w_1(u),\cdots,w_J(u))$是一组可学习得权重函数

聚合操作和卷积表示为

$$D_j(x)f=\sum_{y\in\mathcal{N}(x)}w_j(\mathbf{u}(x,y))f(y),\quad j=1,\ldots,J\\ (f\star g)(x)=\sum_{j=1}^Jg_jD_j(x)f$$

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

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

$$\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}-\boldsymbol{\mu}_j)^\top\boldsymbol{\Sigma}_j^{-1}(\mathbf{u}-\boldsymbol{\mu}_j))$$

其中$\Sigma_j,\mu_j$是可学习的高斯分布协方差矩阵与均值

于是图卷积可表示为

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

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