GCN (Graph Convolutional Network) 图卷积网络解析

目的：图卷积网络近两年大火，博主实习需要用到。接下来几个月就会在图卷积网络上做很多东西。这篇是刚开始对图卷积网络的学习，所以会广泛参考相关论文与网上的技术博客，总结归纳，希望提炼出有用的知识，加深对于图卷积网络的理解。重要内容链接会贴出方便大家学习，也很欢迎大家跟我探讨或者分享心得。对于复杂的公式与繁杂的推证，博主希望尽可能理解其意义，对于难以理解的或者暂时没有时间推证的可以先记下其结论，方便后续

祥瑞Coding

82996人浏览 · 2019-04-16 11:37:33

祥瑞Coding · 2019-04-16 11:37:33 发布

目的：图卷积网络近两年大火，博主实习需要用到。接下来几个月就会在图卷积网络上做很多东西。这篇是刚开始对图卷积网络的学习，所以会广泛参考相关论文与网上的技术博客，总结归纳，希望提炼出有用的知识，加深对于图卷积网络的理解。重要内容链接会贴出方便大家学习，也很欢迎大家跟我探讨或者分享心得。对于复杂的公式与繁杂的推证，博主希望尽可能理解其意义，对于难以理解的或者暂时没有时间推证的可以先记下其结论，方便后续推证以及对方便对图卷积网络的运用。概览尽可能解释清楚重要的概念及相关知识，方便后续更深入的理解。

结论：除了推证繁杂之外，图卷积的结论非常简洁易懂，物理意义很明确。

可参考代码：https://github.com/Megvii-Nanjing/ML_GCN 这个代码之中的GCN的代码

三、图卷积Graph convolution

3.1 傅立叶与卷积的性质

3.2 图的傅立叶变换的矩阵形式

3.3 图卷积Graph convolution

3.4 图卷积网络

3.5 卷积层公式

3.6 图卷积网络公式

一、CNN与GCN

这部分我们介绍下GCN的由来，为了处理图Graph的神经网络。同时引出用图来处理的方法。

1.1处理数据结构不同

欧几里得结构：CNN处理的数据是矩阵形式，就是以像素点排列成的矩阵为基础。称为Euclidean Structure，欧几里得结构。

拓扑结构(图结构)：GCN处理的数据是图结构，即Non Euclidean Structure非欧几里得结构，拓扑结构。如社交网络连接，信息网络等等。对于Non euclidean structure的数据，卷积神经网络就没有用了。

1.2 特征提取

https://www.zhihu.com/question/54504471

卷积提取特征

对于卷积神经网络CNN，图片中提取特征，可以采用卷积的方式提取特征。但是对于拓扑结构，只能用其他方法来提取特征。

对图的特征提取分为vertex domain(spatial domain)空域和spectral domain频域。

对于图结构的提取信息，也可以用谱聚类的方法，我们暂不讨论：https://www.cnblogs.com/pinard/p/6221564.html

空域方法vertex domain

vertex domain(spatial domain)，很直观，直接用相应顶点连接的neighbors来提取特征。

Learning Convolutional Neural Networks for Graphs http://proceedings.mlr.press/v48/niepert16.pdf

频域方法（谱方法）spectral domain

这个就是GCN，即图卷积网络所采用的方法。

GSP（graph signal processing）图形信号处理的方法，即在图上进行信号处理的变换，如傅立叶变换或者拉普拉斯变换，进而进行图的卷积，从而提取图的特征。博主本科是通信工程出身，因此对傅立叶变换、拉普拉斯变换等等这种信号处理的方式还是挺熟悉的。理解上障碍没有那么大，简而言之就是将相应的信号转换到另一个域去分析，从而获得更好的分析结果。如果不懂的话可以去查阅相应的《信号与系统》或者傅立叶变换，拉普拉斯变换这些方面的知识。

GSP（graph signal processing）图形信号处理，顾名思义就是将图当做信号，然后运用信号处理的方法去分析与处理Graph的特征。借助于图的拉普拉斯矩阵的特征值和特征向量来研究Graph的性质.

二、图卷积理论基础

简单而言，只要弄懂两个工具，一个是Laplace, 一个是Fourier，就懂了图卷积，并且除了推证比较繁杂之外，图卷积的结论非常简洁。

在GCN之中，拉普拉斯变换和傅立叶变换起到了非常重要的作用。其中涉及非常多矩阵论、高等代数、信号处理的知识。我们不可能从底层一步一步的推导出公式，只能按照top-down的方法，尽量理解与运用其成型的结论。

2.1 图的拉普拉斯矩阵

对于图 G=(V,E) ，其Laplacian 矩阵的定义为 L=D-A ，

L为拉普拉斯矩阵Laplacian matrix
D为对角度矩阵Degree matrix，对角线上的元素是顶点的度，即该元素链接的元素的个数
A为邻接矩阵 Adjacency matrix ,即表示任意两个顶点之间的邻接关系，邻接则为1，不邻接则为0
这个结论是个重要的结论，我们暂不具体推证，只是理解一下其中的物理意义。

物理意义：这个矩阵描述图的拉普拉斯矩阵与图的性质之间的关系。拉普拉斯矩阵与图的性质满足 L=D-A 这种矩阵关系，其中图 G=(V,E) 的性质，体现在图的邻接矩阵A和图的度矩阵D上。

在理解了这个的基础上，还有其他的几种拉普拉斯矩阵，上面这种拉普拉斯矩阵只是其中的一种，下面几种拉普拉斯矩阵在不同的任务中有不同的运用。具体怎么用以后用到再说。

Combinatorial Laplacian
Symmetric normalized Laplacian
Random walk normalized Laplacian

通过上面的公式的物理意义，我们知道了，图的性质可以表示在拉普拉斯矩阵之中，即图的性质可以通过拉普拉斯矩阵体现出来。这样，我们将图的分析，可以变为对拉普拉斯矩阵的分析。

这节的重点就是：图的性质——图的拉普拉斯矩阵的性质，之间的对应关系，以及拉普拉斯矩阵如何求得。

2.2 傅立叶变换

https://zhuanlan.zhihu.com/p/54505069

拉普拉斯矩阵与傅立叶变换是GCN的两大理论基础。做过信号处理的会比较熟悉傅立叶变换。如果不熟悉也没关系，简单来说，傅立叶变换就是通过傅立叶变换，将一个域的信号转换到另一个域，便于我们分析与运算。

傅立叶变换的定义：，就是一种变换方式，将信号由t域变换到w域。

为什么要引入傅立叶变换？因为傅立叶变换具有一定的性质，就是原域进行卷积，相当于频域相乘：

即一个域相乘，相当于另一个域卷积；一个域卷积，相当于另一个域相乘。算图域卷积相当于傅立叶域相乘，那先对图和卷积核做傅立叶变换后相乘，再傅立叶反变换回来，就得到了图域卷积。

2.3 傅立叶变换与拉普拉斯矩阵的关系

傅立叶变换与拉普拉斯矩阵的关系：传统傅立叶变换的基，就是拉普拉斯矩阵的一组特征向量。这个具体推证我们不具体推证，但是这也是一个重要的结论，这在描述一种转化的关系，从求傅立叶变换的基得这个问题转换到求拉普拉斯矩阵的特征向量这个问题。

用公式描述就是下面这样，我们可以记下结论并且理解其中的物理意义：

，

再写清晰一点，就是

U就是L的特征向量，也是傅立叶变换的基，，也是正交矩阵
L的特征值组成的对角矩阵：
结论：拉普拉斯矩阵的特征向量是傅立叶变换的基

通过这个结论，图的傅立叶变换就写成了另一种形式

图的傅立叶变换就变为：

图的第i个点上的signal为f(i)
图x表示为
互为对偶向量是 $u_{l}$ 的的对偶向量（线性代数的知识）
其中 $u_{l}^{*}$ 是矩阵 $U^{T}$ 的第行， $u_{l}$ 是矩阵的第行

问题的转换：傅立叶变换的基——拉普拉斯矩阵的特征向量——拉普拉斯矩阵的谱分解（特征分解）

图的傅立叶变换——图的傅立叶变换的矩阵形式

2.4 GCN最重要结论

因此，依据前面这些结论，我们得出了最重要的结论，图的傅立叶变换的矩阵形式：

针对图x的傅立叶变换，写作傅立叶变换基乘以图（傅立叶变换基也是拉普拉斯矩阵的特征向量们）

用前面复杂的傅立叶变换以及拉普拉斯变换的种种性质，我们得到了一个简洁而且非常重要的结论。就是上面这个公式，图的傅立叶变换。

同理，反傅立叶变换

反傅立叶变换的矩阵形式

理解了前面这些结论，这几个公式简洁明了，也是GCN的理论基础。

三、图卷积Graph convolution

前面得到了两个特别简洁的结论，结合起来，就是图卷积的理论。

3.1 傅立叶与卷积的性质

傅立叶变换的性质中相当重要的结论就是：

即一域卷积，相当于另一域相乘。其中的逻辑关系等价：图域卷积——频域相乘。中间的桥梁就是傅立叶变换与反傅立叶变换。

3.2 图的傅立叶变换的矩阵形式

，这个就是我们前面得到的简洁明了的公式：图的傅立叶卷积的矩阵相乘形式，其中U既是傅立叶变换的基底，也是拉普拉斯矩阵的特征向量。

此公式写清晰一点，就是：

graph上的N维向量为f，每个顶点为f(i)
第个特征向量的第个分量为，这个既是傅立叶变换的基也是拉普拉斯矩阵的特征向量
特征值频率为 $\lambda_l$
复数空间的内积采用了，也就是特征向量的共轭

3.3 图卷积Graph convolution

结合上面3.1与3.2的内容，我们得出图卷积最重要的结论：

g就是 filter函数，也就是卷积核
图x表示为，即图在每一点上面的信号
U即是傅立叶变换的基，也是拉普拉斯矩阵的特征向量

其中理论基础为：算图域卷积相当于傅立叶域相乘，那先对图和卷积核做傅立叶变换后相乘，再傅立叶反变换回来，就得到了图域卷积。

傅立叶变换和反傅立叶变换可以写成矩阵相乘的形式，那么对应的图卷积就写成了矩阵乘形式。

我们就得到了图卷积经典论文中的公式 Semi-supervised classification with graph convolutional networks, ICLR2017 ， https://arxiv.org/pdf/1609.02907.pdf

3.4 图卷积网络

https://blog.csdn.net/chensi1995/article/details/77232019

接下来已经可以看懂对应论文了：

Semi-supervised classification with graph convolutional networks, ICLR2017 ， https://arxiv.org/pdf/1609.02907.pdf

图x与卷积核进行卷积可以写成，

第一个等号的等价，就是上面3.3的公式。
把 $U^{T}g$ 看做是 $g_{\theta}(\Lambda)$ 一个laplacian特征值的函数，参数为 $\theta$
第二个等号的等价在于特征向量与矩阵相乘等于特征向量与特征值多项式相乘。

为了省去大量求特征值特征向量这些运算，我们只对filter函数做近似，这步就是一个为了减少算法复杂度的近似：

，也是

其中 $T_{k}$ 是Chebyshev多项式，K=1就是用切比雪夫多项式进行一阶近似。
可以把 $g_{\theta}(\Lambda)$ 简单看成是 $\Lambda$ 的多项式。

原因： $U\Lambda^{k}U^{T}=(U\Lambda U^{T})^{k}=L^{k}$

卷积也可描述为：

其中为图x的傅立叶域
其中 $\text{diag}(\theta)$ 与相乘即表示 Fourier Domain 上面的点乘
反向乘以 $U^{\top}$ 即从傅立叶域在回到源域

3.5 卷积层公式

设定K=1 ，则卷积层简化为

令 $\tilde{A}=A+I_{N}$ ，这就是一个代数，为了公式简洁这样指代。注意，A是前面提到的邻接矩阵。
令 $\tilde{D}_{ii}=\sum_{j}^{}\tilde{A}_{ij}$ ，则L=，这个是高等代数中的知识。
邻接矩阵获得的代码如下：

def gen_adj(A):
    D = torch.pow(A.sum(1).float(), -0.5)
    D = torch.diag(D)
    adj = torch.matmul(torch.matmul(A, D).t(), D)
return adj

则卷积公式简化为

再加上激活层：

H即层，上标是层数
W为权值矩阵
得出了GCN之中的公式。

# 图卷积层的定义
def forward(self, input, adj):
    support = torch.matmul(input, self.weight)
    output = torch.matmul(adj, support)
    if self.bias is not None:
        return output + self.bias
    else:
        return output

#两层图卷积的定义
    def forward(self, feature, inp):
        feature = self.features(feature)
        feature = self.pooling(feature)
        feature = feature.view(feature.size(0), -1)


        inp = inp[0]
        adj = gen_adj(self.A).detach()
        x = self.gc1(inp, adj)
        x = self.relu(x)
        x = self.gc2(x, adj)

        x = x.transpose(0, 1)
        x = torch.matmul(feature, x)
        return x

为什么小x换为了大X，且θ换为了W，交换了位置？

关于这点，可以参考原论文。小x与大X，θ与W可以看作一一对应的关系，其中类似于滑窗变换一样的操作。类似于，三维卷积可以看作两个滑窗后的大矩阵相乘。