GCN初识
重新回到这里，开始学GNN与GCN。对GCN最初的影响应该就是ENSP中那默默无闻的第一名的解决方案了，那时候不懂它的高深精妙，现在看完GCN回来只觉得太强啦。
一，图神经网络
NLP的数据可以近似理解成一维，CV的数据可以近似理解成二维，还有一些奇奇怪怪的数据可以理解成更高的维度，但是这些数据都是属于欧几里得数据(Euclidean data)。这个概念可以简单理解成，我可以把数据塞进一个序列或者矩阵or一个张量。
但是实际生活中有很多数据不属于欧里几得数据，就比如之前ensp的蛋白质结构（固然你可以把它提取成体素特征，但是其中会损失很大的信息）、社交网络和网页排名（《数学之美》这本书里面较为详细地讲过）。这类复杂的非欧几里得数据(non-Euclidean)，没有上下左右，没有顺序，没有坐标参考点，难以用方方正正的矩阵张量表示。
对于这些非欧数据，离散数学里面的图是一个很好的表达方式，但是之前提到的经典深度模型CNN、RNN却无法很好的处理图形式的数据，因此GNN应运而生。
1，数据与特征
无论是在经典的机器学习还是深度学习中，数据与特征永远是最重要的。
对于图的概念这里不再说了，至少我个人觉得我离散数学学的也不错，数据结构凑合着也还行。
这里面的数据表达最重要的就是节点特征的表示和图的表示。
1.1，图的表示
邻接矩阵是我最先想到的图数据表达方式，它可以把图映射到一个欧式数据中。但是如果对它进行像CV一样的卷积，那会遇到一个很难绷的问题：置换不变性
这种XX不变性最开始的接触就是卷积里面的平移不变性和旋转不变性。不变性意味着即使目标的外观发生了某种变化，但是你依然可以把它识别出来。通俗的讲，我给你一张图片，你识别出来这是只狗，我将图片旋转之后再给你，你依旧可以识别出来这是只狗。这就叫做具有旋转不变性。
上面两张图片看上去截然不同，卷积的结果也一定不同，但是实际上是同一个图的连接矩阵，只是节点的顺序换了。所以置换不变性也很简单，我们要学习到的函数\(f\)，无论输入的邻接矩阵怎么变化，输出都是一样的。
当然，邻接矩阵的存储也是一个很大的问题，邻接矩阵是一个很经典的稀疏矩阵，当节点数来到几千上万时，存储这样一个矩阵就是一个开销很大的事情了，这时候就要用邻接表了。
除此之外还有一个节点度数矩阵。简单来说节点度数矩阵是 \(D\) 是一个 \(n \times n\) 的对角矩阵，其中 \(n\) 是节点数量。\(D_{i,i}\) 表示节点 \(i\) 的度数（即与该节点相连的边的数量）。
1.2，节点的表示
之前一些常见的结点编码成向量的方式，比如说One-hot 向量，数值向量都很好，但是有个问题：没有考虑到节点之间的位置信息。
而嵌入向量可以较好地弥补这一部分，关于嵌入向量的详细部分，可以参考我前面写的transformer。这里只说在NLP中，要求语义相近的词相近。这里需要位置相近的节点嵌入向量相近。这一点是如何实现的会在后文中提及，这里先不说了。
2，GNN模型
下面是一个简单的两层的 GNN 模型，用于节点分类任务。其中使用的是简单的全连接层和 ReLU 激活函数。同时我也先删去了训练方法（后面再说）。
import numpy as np
class GNN:
def __init__(self, input_dim, hidden_dim, output_dim):
self.input_dim = input_dim
self.hidden_dim = hidden_dim
self.output_dim = output_dim
self.weights1 = np.random.randn(input_dim, hidden_dim)
self.bias1 = np.zeros(hidden_dim)
self.weights2 = np.random.randn(hidden_dim, output_dim)
self.bias2 = np.zeros(output_dim)
def forward(self, adj_matrix, node_features):
h1 = np.dot(adj_matrix, node_features)
h1 = np.dot(h1, self.weights1) + self.bias1
h1 = np.maximum(h1, 0)
h2 = np.dot(adj_matrix, h1)
h2 = np.dot(h2, self.weights2) + self.bias2
h2 = np.maximum(h2, 0)
pooled_features = np.sum(h2, axis=0)
return pooled_features
前面的init()方法很好理解，就是简单定义模型的输入隐藏输出维度。其中的input_dim是节点的特征维度，output_dim就是标签的特征维度。
而后面的前向计算，就设计到我们下面要讲的消息传递了。
2.1，消息传递
讲到消息传递之前我们先要讲讲CNN中的局部性，汇聚与组合。
在图像数据中，我们已经有种先验知识：相邻像素之间有很强的相关性，即相邻像素之间的值很可能是相似的。这被称之为局部性，CNN利用这种局部性，将卷积核与图像的不同部分进行卷积操作来提取特征。
汇聚操作则是其中的pooling池化，准确的说是一种降采样技术，对卷积的输出进行汇聚，降低特征图尺寸的同时，尽可能地保留他的有效特征。
组合操作指的是将特征图中的不同特征进行组合，产生新的更高级别的特征。这一过程通常使用全连接层实现。
虽然图不是欧式数据，没有所谓的上下左右之分，但是图中的每个节点也同样的和他周围的多个点相关。因此在GNN中，每个节点的特征都可以看作是一种局部的表示，而不是全局的表示。不同于CNN中通过卷积层逐层提取图像中的局部特征，GNN通过图卷积层来聚合邻居节点的特征信息，从而得到节点的全局表示。而其中的聚合操作就是 np.dot(adj_matrix, node_features) 邻接矩阵乘以节点特征矩阵，聚合邻居节点特征。
2.2，节点嵌入的计算
前面虽然也提过一点节点嵌入，但是觉得应该放在消息传递以后讲可能会比较合适，所以拆开成两段了。这一段的公式比较复杂，或许代码会比公式好理解很多。这里的节点嵌入类似于一个编码器，像之前transformer中写的单词编码一样，用一层（或多层）全连接层进行映射。
在正式介绍节点的嵌入之前，我们需要明白一个概念：汇聚权重，这可以理解成对邻接矩阵的一个修正。
当我们简单的用邻接矩阵进行消息传递的时候，比如下面：
\[Ax= \left[\begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{matrix}\right] \left[\begin{matrix} 0 \\ 1 \\ 2 \\ 3 \end{matrix}\right]= \left[\begin{matrix} 6 \\ 2 \\ 1 \\ 0 \end{matrix}\right]\]就会发现存在3个邻居的节点0，它计算了上次，这意味在信息传递以后，会更加倾向于节点0。同时越来越大的最大值，也会抑制其他节点特征训练。这似乎不太合适，这时候取平均就是最好的想法了。取平均的时候，我们可以用到使用度矩阵\(D\)，使用度矩阵\(D\)度矩阵是对角矩阵，对角线表示了每个节点存在几个邻居，其余位置均为0。
将\(A\)除以度数\(D\)，也就是乘以逆矩阵\(D^{-1}\) 。
\[D^{-1}Ax= \left[\begin{matrix} \frac{1}{3} & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\right] \left[\begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{matrix}\right] \left[\begin{matrix} 0 \\ 1 \\ 2 \\ 3 \end{matrix}\right]= \left[\begin{matrix} 2 \\ 1 \\ \frac{1}{2} \\ 0 \end{matrix}\right]\]这样似乎看上去就好很多了，但是我们依然忽略了两个问题：1，这种邻接矩阵只考虑了邻居，没考虑自己。2，这种左乘只考虑了行没考虑列（联系线性代数的初等矩阵左乘和右乘的区别）。
那么现在我们对这个公式做最后的修正，汇聚权重\(B_{k}\)定义为：
\[B_{k}=\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}\]其中\(\widetilde{A}=A+I\)。
最后的最后我们可以得到GCN的公式：
\[H^{l+1}=\sigma(B_{k}H^{l}W^{l})\]其中的\(H\)是之前的嵌入节点，\(W\)是可训练权重。
其实，实际上GCN分为两大类空间的(Spatial)和谱(Spectrum)的，前者通过消息消息交换进行节点嵌入更新，后者则通过傅立叶变换到频域进行处理再逆变换。本文之前的内容主要是基于空间的，基于谱的以后有可能会看看吧。
同时特征表示里面还有一个图拉普拉斯矩阵，emmm，也下次一定吧。下次可能就是大四了。