点击上方“码农突围”，马上关注

这里是码农充电第一站，回复“666”，获取一份专属大礼包

真爱，请设置“星标”或点个“在看”

来源：知乎

作者：Orangrass

链接：https://zhuanlan.zhihu.com/p/54505069

前言

图卷积网络Graph Convolutional Network，简称GCN，最近两年大热，取得不少进展。

最近，清华大学孙茂松教授组在 arXiv 发布了论文 Graph Neural Networks: A Review of Methods and Applications ，作者对现有的 GNN 模型做了详尽且全面的综述。GCN就是GNN中的一种重要的分支。

但是对于GCN的萌新，看着这篇综述可能还是会困难重重、不知所措。

写这篇文章的目的，就是帮助萌新们掌握GCN的重要概念和理论，走出新手村。

什么是Convolution

Convolution的数学定义是：

一般称g为作用在f上的filter或kernel

一维的卷积示意图如下：

大家常见的CNN二维卷积示意图如下：

在图像里面卷积的概念很直接，因为像素点的排列顺序有明确的上下左右的位置关系。

那在抽象的graph里面卷积该怎么做呢？

比如这个社交网络抽象出来的graph里面，有的社交vip会关联上万的节点，这些节点没有空间上的位置关系，也就没办法通过上面给出的传统卷积公式进行计算。

Fourier变换

为了解决graph上卷积计算的问题，我们给出第二个装备--Fourier变换。

先上结论，根据卷积定理，卷积公式还可以写成：

这样我们只需要定义graph上的fourier变换，就可以定义出graph上的convolution变换。

好的，先来看下Fourier变换的定义：

Inverse Fourier变换则是：

根据Fourier变换及其逆变换的定义，下面我们来证明一下卷积定理

我们定义    是    和    的卷积，那么

  

带入    ;   
  

最后对等式的两边同时作用    ，得到

Laplacian算子

一波未平，又来一个陌生的概念。

不要担心，这是出新手村之前的最后一件装备了。

一阶导数定义为：

laplacian算子简单的来说就是二阶导数：

那在graph上，我们可以定义一阶导数为：

其中y是x的邻居节点

那么对应的Laplacian算子可以定义为：
 

定义    是   的度数矩阵(degree matrix)

定义    为   邻接矩阵(adjacency matrix)

那么图上的Laplacian算子可以写成

标准化之后得到   

定义Laplacian算子的目的是为了找到Fourier变换的基

比如传统Fourier变换的基    就是Laplacian算法的一组特征向量

  ,    是一个常数

那么图上的Fourier基就是    矩阵的n个特征向量    ，    可以分解为

其中    是特征值组成的对角矩阵

 

那么Graph Fourier变换可以定义为

其中    可以看做是作用在第    个点上的signal，用向量  

  来表示

  是的对偶向量，    是矩阵    的第    行，   是矩阵    的第    行。

那么我们可以用矩阵形式来表示Graph Fourier变换

类似的Inverse Graph Fourier变换定义为

它的矩阵形式表达为

推导Graph Convolution

走到这里，我们已经获得了新手村的所有装备，下面就开始推导GCN的公式。还记得我们之前提到的先上卷积定理吗？

那么图的卷积公式可以表示为：

作为图卷积的filter函数    ，我们希望具有很好的局部性。就像CNN模型里的filter一样，只影响到一个像素附近的像素。那么我们可以把    定义成一个laplacian矩阵的函数   

作用一次laplacian矩阵相当于在图上传播了一次邻居节点。进一步我们可以把    看做是    一个laplacian特征值的函数。

改写上面的图卷积公式，我们就可以得到论文SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS（链接：https://arxiv.org/pdf/1609.02907.pdf）的公式(3)

可以看到这个卷积计算的复杂度是非常高的，涉及到求laplacian矩阵的特征向量，和大量的矩阵计算。下面我们考虑对filter函数做近似，目标是省去特征向量的求解

其中    是Chebyshev多项式。这里可以把简单    简单看成是    的多项式。

因为

所以上面filter函数可以写成    的函数

设定   那卷积公式可以简化为

令    ，   

那么再加上**层，我们就可以得到最终的GCN公式：

---END---

重磅！码农突围-技术交流群已成立

扫码可添加码农突围助手，可申请加入码农突围大群和细分方向群，细分方向已涵盖：Java、Python、机器学习、大数据、人工智能等群。

一定要备注：开发方向+地点+学校/公司+昵称（如Java开发+上海+拼夕夕+猴子），根据格式备注，可更快被通过且邀请进群

▲长按加群

如有收获，点个在看，诚挚感谢