title: GCN学习笔记
categories:
- 生物信息学
date: 2023-03.13
hidden: true
mathjax: true
GCN
GCN(Graph Convolutional Network) ，图卷积网络，是深度学习算法应用最成功的领域之一。图卷积网络其实就是一个特征提取的过程，要学习图卷积，不妨先来来一维的卷积神经网络的原理是什么样的。下面我们来看一个例子。
现在我们假定这样一个场景，有一个信号发生器，每一秒会射一个信号 \(s_i\)。我们记录 t 秒，我们用一个向量记录 t 秒内发生器产生的信号
\[x = [s_1, s_2,...,s_t] \]然后我们有一个信号接收器，这个接受器会接受之前所有发生器发射的信号，但是因为信号的强度会随时间衰减，所以实际上并不能接受之前所有的信号。我们假设这个信号的衰减强度 每过一秒减少一半，信号量为1/4之后消失。即衰减率分别为 \(w_1 = 1, w_2 = 1/2, w_3 = 1/4, w_4 = 0\) 。现在我们用接收器来接受信号，并且从第1秒开始记录 到t秒，请注意信号发生器和信号接收器是同时部署的。我们可以用一个向量记录接受器接受到的信号
\[y = [S_1, S_2,...,S_t] \]我们来看看 \(S_1, S_2, S_3, S_4\) 的信号量分别是多少。
\[S_1 =& s_1 \cdot w_1 \\ S_2 =& s_1 \cdot w_2 + s_2 \cdot w_1 \\ S_3 =& s_1 \cdot w_3 + s_2 \cdot w_2 + s_3 \cdot w_1 \\ S_4 =& s_2 \cdot w_3 + s_3 \cdot w_2 + s_4 \cdot w_1 \]以图像的方式就是下面这样
某一时刻 \(S_i\) 的接受量也可以表示出
\[S_i = \sum_{k=1}^{3} w_k \cdot s_{i-k+1} \]这个系数组合 \([w_1, w_2, w_3]\) 被称为卷积核。到此我们就把发射器中的信号信息提取到了接收器中，这个过程可以理解为一个特征提取的过程，当然卷积不仅仅可以做特征提取，根据卷积核的不同，它可以行使许多功能。如滤过高频/低频信息。
接下来，我们来了解下二维的CNN是如何工作的
Source Pixel 表示的是待提取特征的数据，可以给他赋予一些含义，如这是一张图片三原色中某一色的色值，三张这样的图片可以组成一张完整图片。然后我们现在给这个数据进行卷积提取特征的过程，就是将这个子图局部颜色特征提取到下一层，下一层数据的每一个点都包含了上一层数据的局部特征。中间Convolution 即为卷积和，也是一个系数矩阵。用这个系数矩阵（卷积核）去历遍SourcePixel即可以得到下一层的数据。上图中一下层的数据的维度会比原始数据维度低一些，这个取决于卷积核和步长等等因素，这个大小是可以调整的，如果你想，下一层的数据维度也可以比原始数据高。经过多层的特征提取后，最后我们会得到一个m维的向量，这个向量就是这张图的特征向量，然后用这个向量去做正常的机器分类。
好了，到此为止你已经理解了CNN，而GCN和CNN的区别就是，GCN将CNN应用到了图结构。原来的CNN应用的原始数据必须是满足欧式距离的网络，而GCN则重新定义了卷积核使其满足了有着非欧式距离的图结构
举个例子，在CNN，最核心的一部分就是一个固定的，可平移的卷积核（系数矩阵）。事实上CNN就是全连接网络的缩小版，但在图结构上，如何将这个卷积核进行移动？因为图结构中每个节点的连接数量不一样，如果你的卷积核是一个 \(3 \times 3\) 的九宫格，那么他至少需要9个参数，但在图结构中，你不一定能保证每一个节点都有9个边，难以进行卷积。如何解决这个问题？
解决这个问题非常简单，我只需要对每一个中心节点定义出9个节点（假设我的卷积核是九宫格，当然这是随意的，上图是5个点），这9个节点可以是离中心点最近的九个（当然如何定义距离也是可选择的）。然后给这个九个节点排序，从近到远。这样就实现了参数共享。如果中心节点的边不足9，可以从他的二级连接点中选取。然后我们历遍所有节点，就实现了卷积。
卷积之后，新产生的节点特征就整合了原来图中所有他邻居的特征。然后我们就可以拿这个特征向量去做普通的机器学习。
现在我们来看看图卷积神经网络(GCN)的公式，来深刻的认识一下
\[X' = D^{-\frac{1}{2}}AD^{-\frac{1}{2}}XW \]我们来举一个例子一步一步推导。现在我有这样一个图网络：
一共是四个节点，每个节点我们假设他有一个特征向量，比如A，B，C，D 是四个人，他们的边是他们的社会关系，有边代表认识，无边代表不认识，特征向量就是每个人的身高，年龄，体重等固定的属性。我们假设这四个节点的特征向量如下：
\[X_a = [d_{a1},d_{a2},...,d_{ad'}] \\ X_b = [d_{b1},d_{b2},...,d_{bd'}] \\ X_c = [d_{c1},d_{c2},...,d_{cd'}] \\ X_d = [d_{d1},d_{d2},...,d_{dd'}] \\ \]有 \(X = [X_a,X_b,X_c,X_d]^T\) X是一个特征向量的矩阵。同时我们也写出这个图的邻接矩阵：
\[A= \begin{bmatrix} 0&1&1&1\\ 1&0&1&0\\ 1&1&0&0\\ 1&0&0&0 \end{bmatrix} \]那么 \(AX\) 就是一个 \(4 \times d'\) 维的矩阵，他表示的是经过聚合的四个节点的新的“特征向量”。这个新的特征向量聚合了A邻居的特征信息。我们来写写看
\[X' = AX= \begin{bmatrix} X_b+X_c+X_d\\ X_a+X_c\\ X_a+X_b\\ X_a \end{bmatrix} = \begin{bmatrix} X'_a\\ X'_b\\ X'_c\\ X'_d \end{bmatrix} \]这个聚合的步骤只是将每个节点的邻居加了起来，或许我们可以给他平均一下，避免他的值过大。如何平均？当然是除以相加节点的数量，即要得到下面这样的式子
\[\begin{bmatrix} \frac{X'_a}{3}, \frac{X'_b}{2}, \frac{X'_c}{2}, \frac{X'_d}{1} \end{bmatrix}^T \]显然每个新的“特征向量”除的值是这个节点的度。我们来写成矩阵的形式，在此之前先定义一个度矩阵。为了美观我们之后写成对角的形式
\[D = \begin{bmatrix} 3&0&0&0\\ 0&2&0&0\\ 0&0&2&0\\ 0&0&0&1 \end{bmatrix} = diag(3,2,2,1) \]那么我们的 \(X'\) 现在看起来是这样的
\[X' = D^{-1}AX = \begin{bmatrix} \frac{X'_a}{3}, \frac{X'_b}{2}, \frac{X'_c}{2}, \frac{X'_d}{1} \end{bmatrix}^T \]实际上就是对特征向量X做一个系数变换这个系数就是 \(D^{-1}A\) ，现在我们来看看 \(D^{-1}A\) 是什么样的
\[D^{-1}A = \begin{bmatrix} 0&1/3&1/3&1/3\\ 1/2&0&1/2&0\\ 1/2&1/2&0&0\\ 1&0&0&0 \end{bmatrix} \]注意到，节点对于每个边的权重是相等的，但事实上是不合理的，显然在我们的例子中，D节点对于A的影响是大于C对A的影响的（因为C节点有更多的连接，分散了其作用），因此如何定义这个权重比较合理？GCN中是这样定义这个权重的——通过两个节点边的数量来定义。如果两个节点所连的边越多，则分配的权重越小。反之越大。用公式来表示就是
\[X' = D^{-1}AD^{-1}X \]我们来看看现在系数矩阵 \(D^{-1}AD^{-1}\) 具体是什么样的：
\[D^{-1}AD^{-1} = \begin{bmatrix} 0&0.16666667& 0.16666667& 0.33333333\\ 0.16666667&0&0.25&0&\\ 0.16666667&0.25& 0& 0&\\ 0.33333333& 0& 0& 0\\ \end{bmatrix} \]AB之间的系数和AC之间的系数是相同，他是如何计算的呢？实际上就是分子为1，分母为A的边乘以B（C）的边即 \(1 /(3 \times 2) = 1/6 = 0.16667\) 。这样这个特征聚合的过程就综合考虑了图的结构以及每条边的权重，边越多的节点赋予的权重越低。那么特征在变换后不至于太小，因此我们给分母开一个根号最后就得到了下面的公式
\[X' = D^{-\frac{1}{2}}AD^{-\frac{1}{2}}X \]同样的我写出系数矩阵的具体值
\[D^{-\frac{1}{2}}AD^{-\frac{1}{2}} = \begin{bmatrix} 0& 0.40824829& 0.40824829& 0.57735027\\ 0.40824829& 0& 0.5& 0&\\ 0.40824829& 0.5& 0& 0&\\ 0.57735027& 0& 0& 0& \end{bmatrix} \]进一步的理解，\(D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\) 本质上就是一个加了权重的邻接矩阵，他的值不是0，1而是每条边的权重
最后我们就可以得到GCN 的完整公式
\[X' = D^{-\frac{1}{2}}AD^{-\frac{1}{2}}XW \]W 是一个可学习的参数。他是一个 \(d' \times d''\) 的矩阵，故新生成的特征向量 \(X'_i\) 是一个 \(d''\) 维的向量。这本质上是一个“全连接的卷积”。
然后最后一个问题是，这个新产生的特征向量矩阵 \(X'\) 中每一个节点的新的特征向量 \(X'_i\) 都是由该节点周围的节点特征所定义出来的，少了自己本身节点的信息。故需要解决这么一个问题。解决方法也很简单，修改一下图结构。使图结构变成下面这样
给每一个节点加上一个自连的边，然后重新计算邻接矩阵和度矩阵，这样就完成了。即
\[\hat{A} = I + A \\ \hat{D} = I + D \\ X' = \hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}XW \]到此为止GCN的基本原理就结束。GCN的本质就是将图中的各种信息提取到节点的特征向量中。用新的特征向量去做分类或者其他进一步的机器学习。
参考链接
https://www.bilibili.com/video/BV13b4y1177W?p=37&vd_source=f6542589d9ad6a0fdefc249425eebad2
https://distill.pub/2021/gnn-intro/
标签：frac,特征向量,卷积,Deep,GCN,算法,DRM,bmatrix,节点 From： https://www.cnblogs.com/lantary/p/17211688.html