图卷积神经网络

图卷积神经网络概述

要将图像上的卷积拓展到图上，需要定义一种新的图卷积方法。然后就演变出了两种方法

• Spectral method：用 spectral domain 来定义卷积。

  • 通过图上的傅里叶变换来定义卷积
  • 主要的挑战是卷积滤波器不是局部化的，这个是个致命的缺点

• Spatial method：用 vertex domain 来定义卷积。类比于图像上的二维卷积，照葫芦画瓢

Spectral method

1. Spectral method for graph convolutional neural networks

1.相关概念

给定一个图 $G=(V,E,W)$ , $V$ 是节点集合，假设有 $n$ 个节点，$W\in R^{n\times n}$ 是邻接矩阵，每个节点还有 $d$ 维特征，$x\in R^{n\times d}$ 是节点们的特征向量矩阵。

Laplacian 矩阵

$L=D-W$ , $D$ 是一个对角矩阵并且 $D_{ii}={\sum }_j{W}_{i,j}$

normalized Laplacian 矩阵

$L=I-D^{-\frac{1}{2}}W{D}^{-\frac{1}{2}}$

2.图上的傅里叶变换

• 图上的傅里叶

傅里叶变换的一系列的正交基 { u l } l = 1 n \{u_l\}_{l=1}^n {ul​}l=1n​ 通过其特征值 { λ l } l = 1 n \{\lambda_l\}_{l=1}^n {λl​}l=1n​ ，然后图 Laplacian 矩阵就可以被对角化 $L=U\Lambda U^T$，其中 $U=[u_1,\cdots ,u_n]$，$\Lambda =diag([{\lambda }_1,\cdots ,{\lambda }_n])$

• 图傅里叶变换

  单个向量 $x\in R^n$ 的图傅里叶变换为 $\hat{x}=U^{T}x$ ，逆变换为 $x=U\hat{x}$

3.定义 spectral domain 上的卷积

卷积定理：两个信号的卷积可以看作他们的傅里叶变换的卷积，如下面公式所示，其中 ${\ast }_G$ 代表卷积算子。

$$x{\ast }_{G}y=U((U^{T}x)\odot (U^{T}y))$$

其中 $\odot$ 代表 point-wise 乘积，spectraldomain 里的卷积核就是 $U^{T}y$ 。

令 $U^{T}y=[{\theta }_0,\cdots ,{\theta }_{n-1}]$ 并且 $g_{\theta }=diag([{\theta }_0,\cdots ,{\theta }_{n-1}])$ ，我们有

$$x{\ast }_{G}y=U{g}_{\theta }{U}^{T}x$$

到此可以写出 Spectral Graph CNN，

$$x_{k+1,j}=h(\sum _{i=1}^{f_k}U{F}_{k,i,j}{U}^T{x}_{k,i}),j=1,\cdots ,f_{k+1}$$

其中 $x_{k,i}$ 式第 $k$ 层的信号向量，$F_{k,i,j}$ 是第 $k$ 层的 filter。

4. Spectral graph CNN 的缺点

• 要求出 Laplacian 矩阵的特征分解，要显式的求出矩阵 $U$ 。
• 矩阵相乘的次数太多，计算复杂度太高。是 $O(n^2)$
• 不是局部化的，用的信息不是局部点的信息。

2.ChebyNet: parameterizing filter

为了解决 spectral graph cnn 的三个缺点，考虑用多项式近似参数化卷积核，

$$g_{\theta }=diag([{\theta }_0,\cdots ,{\theta }_{n-1}])\to g_{\beta }(\Lambda )=\sum _{k=0}^{K-1}{\beta }_k{\Lambda }^k,\Lambda =diag({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n)$$

$$x{\ast }_{G}y=U{g}_{\beta }(\Lambda )U^{T}x=\sum _{k=0}^{K-1}{\beta }_k{L}^{k}x$$

这样形式有几个好处

• 不需要做特征分解了。
• 计算复杂度从 $O(n^2)$ 降到了 $O(|E|)$ 。
• 卷积运算是局部的了，因为有 $L^{k}x$ 的操作

Spatial method

通过与图像上的卷积神经网络类比。图像上的卷积步骤：

1. 确定领域。
2. 给领域定序。
3. 参数共享。

通过类比，确定了图卷积神经网络（spatial method）的步骤：

1. 对于每个节点，从它的邻居们中选出固定个数的节点作为邻居。（一阶邻居不够二阶来凑）
2. 按距离来定序。
3. 参数共享。

1.GraphSAGE

• Sampling neighbors
• Aggregating neighbors

a v ( k ) = A G G R E G A T E ( k ) ( { h u ( k − 1 ) : u ∈ N ( v ) } ) a_v^{(k)}=AGGREGATE^{(k)}(\{h_u^{(k-1)}:u\in \mathcal{N}(v)\}) av(k)​=AGGREGATE(k)({hu(k−1)​:u∈N(v)})

$$h_v^{(k)}=COMBIN{E}^{(k)}(h_v^{(k-1)},a_v^{(k)})$$

因为有了聚合函数，就不再需要给邻居定序了。（是 GCN 到 GNN 的过渡）

2.GCN: Graph Convolution Network

• 通过规范化的 Laplacian 矩阵聚合信息。
• 在特征变换里共享参数。
• 是 ChebyNet 的一阶推导。

$$Z=f(X,A)=softmax(\hat{A}Relu(\hat{A}X{W}^{(0)})W^{(1)})$$

GCN 里面其实没有参数化的卷积，其中 $W^{(0)}$ 和 $W^{(1)}$ 是用来做特征变换的，类似全连接神经网络。唯一一个起到卷积作用的是 $\hat{A}$，是图的规范化的 Laplacian 矩阵，是一个给定的矩阵，相当于卷积的硬编码。

3.GAT: Graph Attention Network

https://doi.org/10.48550/arXiv.1710.10903

为了解决 GCN 中没有可学习的卷积参数的问题。

• 通过注意力机制学习一个聚合矩阵，在上面的 GCN 里聚合矩阵就是 Laplacian 矩阵。

• 通过两个部分共享参数。

  1. 特征变换部分的参数 $W$
  2. 注意力机制的参数 $\vec{a}$

$${\alpha }_{i,j}=exp(LeakyRelu({\vec{a}}^T[W\overrightarrow{h_i}||W\overrightarrow{h_j}]))/\sum _{k\in {\mathcal{N}}_i}exp(LeakyRelu({\vec{a}}^T[W\overrightarrow{h_i}||W\overrightarrow{h_k}]))$$

|| 代表拼接操作。

3.MoNet: A general framework for spatial methods

空间方法的一般框架

• 定义多个核函数，无论是否是参数化的。然后衡量中心节点和其他节点的相似度。
• 卷积核是这些核函数的加权和。

$$(f\ast g)(x)=\sum _{j=1}^J{g}_j{D}_j(x)f$$

$g_j$ 是卷积核。

Spectral CNN

$$y=U{g}_{\theta }{U}^{T}x=({\theta }_1{u}_1{u}_1^T+{\theta }_2{u}_2{u}_2^T+\cdots +{\theta }_n{u}_n{u}_n^T)x$$

ChebyNet

$$y=({\theta }_{0}I+{\theta }_{1}L+{\theta }_2{L}^2+\cdots +{\theta }_{K-1}{L}^{K-1})x$$

GCN

$$y=\theta (1-L)x$$

spatial method 和 spectral method 的联系：

都可以由上面的公式概括，$D_j(x)$ 就是核函数，定义了节点之间的相似度和距离。

spatial method 和 spectral method 的不同：

• spectral method 通过显式直接定义出空间变换，投影到谱空间。
• spatial method 直接定义核函数。

Graph Pooling

1.Graph coarsening

• 将节点聚类，将每个簇作为一个代表节点。（应用一些图聚类的方法）
• 节点聚类过程也参数化，文章：https://proceedings.neurips.cc/paper/2018/file/e77dbaf6759253c7c6d0efc5690369c7-Paper.pdf

2.Node selection

• 将节点聚类，从簇中根据测度函数（自定义或者参数化）衡量节点的重要性去选择代表性节点。