原文链接：https://zhuanlan.zhihu.com/p/54505069
清华大学孙茂松教授组在 arXiv 发布了论文Graph Neural Networks: A Review of Methods and Applications，作者对现有的 GNN 模型做了详尽且全面的综述。GCN就是GNN中的一种重要的分支。
一、什么是convolution
Convolution的数学定义是
一般称g为作用在f上的filter或者kernel
一维的卷积示意图如下：
大家常见的额CNN二维卷积示意图如下
在图像中卷积的概念很直接，因为像素点的排列顺序有明确的上下左右位置关系。
那么在抽象的graph里面卷积是怎么做的呢？
比如这个社交网络抽象出来的graph里面，有的社交vip会关联上万的节点，这些节点没有空间上的位置关系，也就没办法通过上面给出的传统卷积公式进行计算。
二、Fourier变换
为了解决graph上卷积计算的问题，我们给出第二个装备--Fourier变换。
根据卷积定理，卷积公式还可以写成
这样我们只需要定义graph上的fourier变换，就可以定义出graph上的conv变换。
先来看一下Fourier变换的定义
Fourier逆变换则是
根据傅里叶变换及其逆变换的定义，下面我们来证明一下卷积定理，我们定义h是f和g的卷积，那么
三、Laplacian算子
又一个陌生的概念
在graph上我们可以定义一阶导数为
定义D为N×N的度数矩阵(degree matrix)
定义A为N×N的邻接矩阵(adjacency matrix)
那么图上的Laplacian算子可以写成L=D-A
标准化之后得到
定义Laplacian算子的目的是为了找到傅立叶变换的基，比如传统的傅立叶变换的基就是Laplacian算子的一组特征向量
那么图上的Fourier基就是L矩阵的n个特征向量U=[u1...un]，L可以分解为，其中
是特征值组成的对角矩阵
那么图傅立叶变换可以定义为
其中f(i)可以看作是作用在第i个点上的signal，用向量来表示，
是
的对偶向量，
是矩阵
的第l行，
是矩阵
的第l行。
那么我们可以用矩阵形式来表示Graph Fourier变换：
类似的Inverse Graph Fourier变换定义为：
它的矩阵形式表示为：
四、推导Graph Convolution
下面我们开始推导GCN的公式。我们之前提到的卷积定理：
那么图的卷积公式可以表示为：
作为图卷积的filter函数g，我们希望具有很好的局部性。就像CNN模型里的filter一样，只影响到一个像素附近的像素。那么我们可以把g定义为一个Laplacian矩阵的函数g(L)
作用一次laplacian矩阵相当于在图上传播了一次邻居节点。进一步我们可以把看做是
一个laplacian特征值的函数，参数为
改写上面的图卷积公式，我们就可以得到论文SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS
https://arxiv.org/pdf/1609.02907.pdf
的公式(3)
可以看到这个卷积计算的复杂度是非常高的，涉及到求laplacian矩阵的特征向量，和大量的矩阵计算。下面我们考虑对filter函数做近似，目标是省去特征向量的求解
最后加上激活层，我们可以得到最终的GCN公式：
网友评论